换币贪心算法未通过测试用例

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] 和 Amount = 12、
贪心取 [2, 3, 7] 最优选择是 [6, 6].

您需要使用动态规划方法来获得最优值。

换币贪心算法未通过测试用例

Coin Change Greedy Algorithm Not Passing Test Case

algorithm

dynamic-programming

greedy

coin-change