硬币更换-Java未能通过示例3

Question

问题：你会得到不同面额的硬币和总金额。写一个函数来计算你需要的最少数量的硬币来组成这个数量。如果这些硬币的任何组合都不能弥补这个金额，返回-1。

例1：

输入：硬币=[1,2,5]，金额=11输出：3解释：11 = 5 5 1

例2：

输入：硬币=2，金额=3输出：-1

你可以假设每种硬币的数量是无限的。

我的代码：

public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    int new_amount=amount;
    int count_coin=0;
    int q=0,r=0,a=0;
    int k=coins.length-1;


    while(amount>0 && k>=0) {

            q = new_amount / coins[k];
            count_coin = count_coin + q;
            r = new_amount % coins[k];
            new_amount=r;
            a+=q*coins[k];
            k--;



    }


    if(a==amount){
        return count_coin;
    }
    else{
        return -1;
    } }

我的代码在给定的两个例子中运行良好。在使用这个示例之后，我使用了另一个测试用例。

示例3：输入：硬币=[186,419,83,408]，金额=6249输出：20我的输出：-1

我不理解这个例子。如果有人对这个例子或任何其他更好的html" target="_blank">算法有任何想法，除了我的，请与我分享。

我看到了硬币兑换（动态规划）链接。但我无法理解。

我还研究了为什么贪婪换币算法对某些硬币集不起作用？但我不明白它想说什么。所以我提出了这个问题。

提前谢谢你。

Answer 1

您的代码使用贪婪的方法，不能正常工作的任意硬币名词（例如，set3,3,4不能产生答案6）

而是使用动态规划方法（示例）

例如，将数组A设置为长度amount 1，将其填充为零，将A[0]=1设置为从第n个条目向下遍历每个硬币的标称数组，为每个单元格选择最佳结果。

伪代码：

 for (j=0; j < coins.length; j++) {
     c = coins[j];
     for (i=amount; i >= c; i--){
          if (A[i - c] > 0)
              A[i] = Min(A[i], A[i - c] + 1);
     }
 }
 result = A[amount] - 1;