0

我试图解决这个问题，给定一定面额的硬币，我想找到最大数量的硬币来找零。

示例假设我得到了价值 3 和 5 的硬币，我想找 15 的硬币，解决方案是 {3,3,3,3,3}（感谢 JoSSte 指出）同样，假设价值 3 和 5 的硬币，我想找 7 的硬币，我需要显示“No solution possible”

我能够做到这一点以找到最少的硬币数量，如下所示

import java.util.ArrayList;
import java.util.Arrays;


public class Minimum
{
    static int[] options = {5,3};

    public static void main(String[] args)
    {
        ArrayList<Integer> result = new ArrayList<Integer>();

        result = fun(15);
        if(result.size() == 999)
             System.out.println("Not possible to make change with this denomination");
        else 
        {
            for(int i = 0;i<result.size();i++)
                System.out.print(result.get(i));
        }
    }

    static ArrayList<Integer> fun(int n)
    {       
        if(n == 0)
        {
            ArrayList<Integer> totalret = new ArrayList<Integer>();
            return totalret;
        }

        if(n < 0)   
        {
            ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
            return totalret;
        }

        ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
        for(int i = 0;i<options.length;i++)
        {
            ArrayList<Integer> reci = fun(n-options[i]);

            ArrayList<Integer> reti = new ArrayList<Integer>();
            reti.addAll(reci);
            reti.add(options[i]);

            if(reti.size() < totalret.size())
                totalret = reti;
        }
        return totalret;
    }
}

请注意，我有一个名为 if(n<0) 的检查，其中不加总和的组合通过将它们的大小设置为不能是最小值的非常大的数字从选项中删除。

但是，我怎样才能修改上面找到最大的硬币数量

4

2 回答 2

1

对于您的解决方案，您必须检查 n=1,2 的条件。如果 n=1,2 您可以将 ans 返回为 999。

您的功能必须如下

 static ArrayList<Integer> fun(int n)
   {       
     if(n == 0)
     {
            ArrayList<Integer> totalret = new ArrayList<Integer>();
            return totalret;
        }

        if(n < 0 || n==1 || n==2)   
        {
            ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
            return totalret;
        }

        ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
        for(int i = 0;i<options.length;i++)
        {
            ArrayList<Integer> reci = fun(n-options[i]);

            ArrayList<Integer> reti = new ArrayList<Integer>();
            reti.addAll(reci);
            reti.add(options[i]);

            if(reti.size() < totalret.size())
                totalret = reti;
        }
        return totalret;
    }

希望这应该工作..

于 2015-09-21T05:11:06.400 回答
0

这是c ++中的硬币兑换dp代码。

int coin[] = {3, 5}; //initialize array
int make;
int dp[2][100];

int call(int i, int amount)
{
     if(i >= 2) { // All coins have been taken
          if(amount == make) return 1;
          return 0;
     }

     if(dp[i][amount] != -1) return dp[i][amount];
     int ret1 = 0, ret2 = 0;
     // try to take coin i
     if(amount + coin[i] <= make) ret1 = call(i, amount + coin[i]); 

     ret2 = call(i+1, amount); // don't take coin i
     return dp[i][amount] = ret1 | ret2; // is possible or not?
}

int main()
{
    make = 7;
    memset(dp, -1, sizeof(dp));
    if(call(0, 0) == 0) cout << "not possible" << endl;
    else cout << "possible" << endl;

    return 0;
}
于 2015-09-22T22:26:40.387 回答