3

给定一组硬币，你如何以最优化的方式达到给定的金额？

假设在这种情况下，我们有 1、5、10、20 和 50 美分硬币的随机数，其中最大的硬币优先。

我的第一个直觉是使用所有可能适合的最大硬币，然后如果超过总和，则使用下一个价值最小的硬币。

这种方法会这样做还是有任何不足之处？有没有更有效的方法？

4

3 回答 3

8

首先简单地分发最大的硬币是有缺陷的。

假设您的自动售货机已售完所有硬币，除了 50c、20c 和 1c 硬币各有 20 个，而您必须交付 60c 的零钱。

“优先级最大”（或贪婪）方案将给您 11 个硬币、1 个 50c 硬币和 10 个 1c 硬币。

更好的解决方案是三个 20c 硬币。

贪心方案只会给你局部最优解。对于全局最优，您通常需要检查所有可能性（尽管可能存在 minimax 类型的算法来减少搜索空间）以确定哪些可能性，对于交付更改，通常完全在可计算性的范围内。

于 2012-10-01T05:05:37.087 回答
3

贪婪算法（你现在正在做的事情）通常被选择用于这类事情，并作为最终状态机实现，用于自动售货机（对于这种特殊情况）。

贪心算法确定在找零时提供的最小硬币数量。这些是人类模仿贪心算法所采取的步骤

于 2012-10-01T05:01:37.903 回答
0

每次用尽最大面额的假设不会是最好的解决方案。例子：

Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents 

Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents (min)
As per logic of exhausting largest coins first, we would end up with one
coin of 9 cents and 2 coins of 1 cent

请参阅此答案以获取更多说明。

于 2016-05-09T12:33:15.047 回答