硬币变化贪婪算法不通过测试用例

Question

我试图解决换硬币的问题，你用尽可能少的硬币来换钱。我尝试使用贪婪的方法——我的算法对硬币数组进行排序，从最大的硬币开始，并尽可能多地使用它，然后再移动到下一个硬币，将剩余的硬币分开。

这对初始测试用例有效：

硬币=[1,2,5]，数量=11

但这次失败了：

硬币=[186,419,83,408]，金额=6249

我不确定它为什么会失败，我仍在努力掌握贪婪的方法。非常感谢您的反馈！

class Solution {
    public int coinChange(int[] coins, int amount) {
        int count = 0;
        
        if(coins.length == 1 && amount % coins[0] != 0) {
            return -1;
        }

        Arrays.sort(coins);
        
        int i = coins.length - 1;
        while(amount >= 0 && i >= 0) {
             if(coins[i] <= amount) {
                int remainder = amount / coins[i];
                    count = count + remainder;
                    amount -= (remainder * coins[i]);
            }
            i--;
        }
    
        return count;
    }
}

Answer 1

例如：
Coins=[2,3,6,7]andAmount=12，
Greedy需要[2,3,7]]而最优选择是[6,6]。

您需要使用动态编程方法来获得最佳值。