硬币更改 - Java无法通过示例3

Question

问题:您将获得不同面额的金币和总金额.编写一个函数来计算构成该数量所需的最少数量的硬币.如果这笔钱不能由任何硬币组合弥补,则返回-1.

例1:

输入:coins = [1,2,5],金额= 11输出:3说明:11 = 5 + 5 + 1

例2:

输入:coins = 2,金额= 3输出:-1

You may assume that you have an infinite number of each kind of coin.

我的代码:

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:输入:coins = [186,419,83,408],金额= 6249输出:20我的输出:-1

我不明白这个例子.如果任何人对此示例有任何想法或除了我的任何其他更好的算法,请与我分享.

我看到了Coin Change(动态编程)链接.但无法理解.

我还研究了为什么贪婪的硬币改变算法不能用于某些硬币组？ 但无法理解它试图说什么.所以我提出了这个问题.

先感谢您.

Answer 1

您的代码使用的贪婪方法对于任意硬币名称都不能正常工作(例如,set 3,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;