问题及解答

假设使用某国的货币（指纸币和硬币）, 要得到 $x$ 元, 要求是使用最少的钞票和硬币. 将这种取法称为最优方案.

比如美国货币, 我们要找出 17 美元 61 美分.

方案:

• 一张 10 元美钞;
• 一张 5 元美钞;
• 两张 1 元美钞;
• 两个 25 分币;
• 一个 10 分币;
• 一个 1 分币.

对于美国货币系统, 可以证明对任意 $x$, 可以找到最优方案.

References:

Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, (Third Edition).

张怀勇 等译, 《数据结构与算法分析 C++ 描述》（第三版） [Chapter 10. Page. 296]