再探找零问题

从同志那里看到的有趣的问题。我觉得有必要探讨一下。

构造一个情况

数字太大不利于我这种计算能力基本没有的人来思考。我们换一个简单的情况。

考虑面额为 [1, 4, 5, 6], 需要找 9 元。容易知道，最佳策略是找 1 个 5 元和 1 个 4 元，而贪心策略是找 1 个 6 元和 3 个 1 元。为什么贪心策略会失败？

为什么贪心会成功

我们反过来思考，为什么贪心在大多数情况下会成功？

这种题目的通解是使用动态规划。我们不妨画出动态规划表格：

容易理解，其单元格驱动函数（粗略）为 f(col, row) = 1 + min(f(col - #row)). 我们再给出喜闻乐见的 [1, 2, 5, 10], 并画出动态规划表格：

注意到被加粗的数字，他们是本列中的最优解。容易发现，对于可以贪心的情况，最优解（之一）一定是最底一行，这使得动态规划退化成为简单的贪心情况。

如果你希望在 Excel 里自己试验不同的金额组合的结果，这是驱动公式：

=IF(B$1-$A2>=0,IF(B$1-$A2=0,1,1+MIN(INDIRECT(CONCAT("R2C",B$1-$A2+1),FALSE):INDIRECT(CONCAT("R5C",B$1-$A2+1),FALSE))),99999)

第一行和第一列用作表头。第一列给出面值组合，第一行则是从 0 开始的自然数序列。

如何构造不能贪心的面值

如果在一个面值体系内存在至少 3 种不同面额、存在一个金额 \(m\) 和某个非最大面额 \(d\), 有 \( m = k \cdot d ~ (k = 2, 3, 4...) \), 且满足对于最大面额 \(D\), \( m - D > 1 \) 且 \( m - D \)不能用除了 1 以外的面额的组合表示，则该金额是不能贪心的。最小的不可贪心面额组为 [1, 3, 4], 6.

不能贪心的金额有限么？

容易想到的问题就是对于不可贪心的面值组合，其不可贪心的金额是有限个么？

直觉上，不可贪心的金额是有限的。但严谨的数学证明有待给出。我们需要证明，存在这样的自然数 \(n, p, q\) 和面额 \(d^{\prime} \lt d\) 使得 \( n \cdot d = p \cdot D + q \cdot d^{\prime} \) 且有 \( n \geq p + q \).