给定一组硬币，您将如何以最佳方式达到给定的总和？
假设在这种情况下，我们有 1、5、10、20 和 50 美分硬币的随机数，其中最大的硬币获得优先权。
我的第一直觉是使用所有可能的最大硬币来装，然后如果超过总和则用完值(value)次小的硬币。
这种方法行得通吗？这种方法有什么缺点吗？有没有更有效的方法？
最佳答案
简单地先分发最大的硬币是有缺陷的。
假设您的自动售货机除了 50 美分、20 美分和 1 美分的硬币各有 20 枚外，所有硬币都卖光了，您必须提供 60 美分的零钱。
“优先最大”(或贪心)方案会给你 11 个硬币，1 个 50c 硬币和 10 个 1c 硬币。
更好的解决方案是三个 20c 硬币。
贪婪方案只会为您提供局部最优解。对于全局最优，您通常需要检查所有可能性(尽管可能有最小最大类型的算法来减少搜索空间)以确定对于交付变化而言，哪些可能性通常完全在可计算性的范围内。
关于algorithm - 最适合给定金额的硬币，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12667721/