再探找零问题

/ 0评 / 0

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

构造一个情况

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

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

为什么贪心会成功

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

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

123456789101112
1123422233333
4---123422233
5----12342223
6-----1234222

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

123456789101112
1122332334423
2-12233233442
5----12233233
10---------122

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

如果你希望在 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 \).

发表评论

电子邮件地址不会被公开。 必填项已用*标注