algorithm - 贪心算法和硬币算法

Question

首先，是的，这是我的硬件，我觉得很难，所以我真的很感激一些指导。

我需要证明对于硬币问题的贪心算法何时总是有效的面额。1,x,x2...xnx>=1

• 当我们总是从数量中选择最大的硬币时，我们总是会以最小的硬币数量获得我们需要的金额。

谢谢你。

Answer 1

由于这是您的作业，因此我不会提供完整的答案，而是会尝试指导您：

首先，因为这种类型的问题通常会发生这种情况，请尝试自己证明该陈述对于前几个自然数是正确的。试着总结一下你用来为他们做证明的东西。这通常会给你一些正确方法的指导。

我会为此使用归纳法。

另一个可能对您有所帮助的选项 - 用 base 表示数字系统中的所有数字x。这应该更清楚为什么该陈述是正确的。

希望这对您有所帮助。