找到赚一笔钱所需的最小硬币数量

Question

给定一美元金额，如何找到该金额所需的最小硬币数量？

示例输入：1.21美元

示例输出：[0.25，0.25，0.25，0.25%，0.1，0.1，0.01]

我在考虑Java 的回溯选项

Answer 1

您可以简单地从最大到最小循环硬币，每次使用尽可能多的硬币。请注意，最好使用美分来避免浮点问题。

static List<Integer> minCoins(int cents){
int[] coins = {25, 10, 5, 1};
List<Integer> result = new ArrayList<>();
for(int coin: coins){
if(cents == 0) break;
result.addAll(Collections.nCopies(cents / coin, coin));
cents %= coin;
}
return result;
}

演示

注意，对于任何一组硬币的一般情况，上述贪婪算法并不总是有效的，需要动态编程。