给定金额的最佳硬币

首先简单地给出最大的硬币存在缺陷。

假设您的自动售货机售罄，除了50c，20c和1c硬币各有20种之外，您必须交付60c的零钱。

“优先最大”（或贪婪）方案将为您提供11个硬币，1个50c硬币和10个1c硬币。

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

贪婪的方案只能为您提供 本地
最佳解决方案。对于全局最优，通常需要检查所有可能性（尽管可能存在minimax类型的算法来减少搜索空间），以确保通常在可计算性范围内进行传递更改。