作者alan23273850 (God of Computer Science)
看板Math
标题Re: [其他] 一题 Codeforces 取硬币演算法反例证明
时间Tue Feb 16 19:26:28 2021
※ 引述《LPH66 ( )》之铭言：
: ※ 引述《alan23273850 (God of Computer Science)》之铭言：
: : 小弟今天正在练习这题 https://codeforces.com/problemset/problem/725/E
: : 解答如下 https://codeforces.com/blog/entry/47974 (第 E 题)
: : 题目是想用增加冗余硬币的方式证明 "贪心法 (优先取大) 取硬币" 并不可行。
: : 举例来说，从 S = {5,4,3} 可以凑出 12，可是 S' = {5,5,4,3} 就不行因为取了前面
: : 两个 5 之後就剩 2，无法由剩下的 4 和 3 取出。而这题增加冗余硬币的最小额度恰好
: : 就是 5 (即 S' 的例子)，题目想问每次增添冗余硬币的最小额度。
: : Q. 增加冗余硬币可以两种币值以上，每种币值 (整数) 至少一枚，但标准解答却说
: : 万一满足最小额度的解答有两种币值以上，它必定可以合成一种币值，也是答案。
: : 换句话说，在找最小额度的时候总是可以假设只增添一种币值，但枚数不限。
: : A. 其实解答和下面的讨论区有附上证明，但是我看不懂！！所以想请问广大资深乡民
: : 可否帮忙指点迷津，让小弟我稍微参透一下他们的想法？
: : 至於要怎麽找币值我应该可以自己顿悟，所以这部分可以先不需要，感谢感谢！
: 他的逻辑是这样的:
: 如果被加入的硬币最大的两个的币值是 x 和 y, x≧y
: 当然这两个硬币会被选 (不然就不用加了)
: 那把这两个硬币换成一个 x+y 的话
: (1) x+y 大於 x, 所以贪心法一定会比选 x 时更早选走 x+y
: 那麽在新组合的贪心法的过程中, 到同样硬币时已选总钱数一定不少於原本的状况
: 於是原本因为溢出不选的硬币在新组合里同样也会因为溢出不选
: (2) 因为 x 和 y 包含在贪心法的选择中
: 因此任意原组合中选中的硬币加上 x 和 y 仍然小於目标
: 也就是说对於原本就选中的硬币在新组合中同样会因为小於目标而被选中
: 因此, 把加入的 x y 两个硬币换成 x+y 一个硬币的话
: 贪心法一样会在同样的组合中失败 (除了 x 和 y 换成 x+y 而已)
: 重覆运用 (ie. 数学归纳法) 即可证明如果有个方法使用多个硬币
: 则这些硬币合成一个也是个方法
我再帮这篇贴文增补一张更平易近人的示意图，以验证我自己的理解！
在 X+Y 之前的硬币因为组态没有改变，所以选择的组合也不会改变，这很自然。
.......______...●...●... implies f(A) + Ｘ + Ｙ <= S
A Ｘ Ｙ
.......[●●]... since f(A) + X＋Y <= S
A X＋Y
而因为上面不等式的成立，所以合并後的 X＋Y 也应该要被选。
.......______○...●...●...
A Ｂ Ｘ Ｙ
.......[●●]○...
A X＋Y Ｂ
如果 X+Y 後方的第１颗硬币Ｂ在Ｘ和Ｙ合并之前没被选，这隐含着 f(A) + Ｂ > S，
那麽合并之後的硬币Ｂ也不能选，因为 f(A) + (X＋Y) + Ｂ 必定也大於 S。
.......______●...●...●...
A Ｂ Ｘ Ｙ
.......[●●]●...
A X＋Y Ｂ
如果 X+Y 後方的第１颗硬币Ｂ在Ｘ和Ｙ合并之前已经被选，那麽本来就应该有：
f(A) + Ｂ + Ｘ + Ｙ <= S，而合并之後的不等式不变，所以也应该要选。
.......______Ｂ○...●...●...
A Ｃ Ｘ Ｙ
.......[●●]Ｂ○...
A X＋Y Ｃ
如果 X+Y 後方的第２颗硬币Ｃ在Ｘ和Ｙ合并之前没被选，则 f(A) + f(Ｂ) + Ｃ > S，
那麽合并之後的硬币Ｃ也不能选，因为 f(A) + (X＋Y) + f(Ｂ) + Ｃ 必定也大於 S。
.......______Ｂ●...●...●...
A Ｃ Ｘ Ｙ
.......[●●]Ｂ●...
A X＋Y Ｃ
如果 X+Y 後方的第２颗硬币Ｃ在Ｘ和Ｙ合并之前已经被选，那麽本来就应该有：
f(A) + f(Ｂ) + Ｃ + Ｘ + Ｙ <= S，而合并之後的不等式不变，所以也应该要选。
按照此要领如法炮制，可以推得 X＋Y 之前和之後的所有硬币都维持不变的选择，
所以也是一个会让贪心法 fail 的答案，得证！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.242.235.50 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1613474791.A.08C.html
1F：→ alan23273850: 这篇和上一篇最大的增补主要是强调顺序性，一定要 02/16 19:30
2F：→ alan23273850: 前一颗硬币维持相同的选择之後我才能开始後面一颗的 02/16 19:30
3F：→ alan23273850: 推导，不然我不放心 02/16 19:30
※ 编辑: alan23273850 (111.242.235.50 台湾), 02/16/2021 19:32:04
4F：推 LPH66 : 嗯, 顺序性这个问题原题解里没有明提 02/17 02:05
5F：→ LPH66 : 是在 (1)(2) 两个理由里隐含了这回事 02/17 02:06
6F：→ LPH66 : 但题解强调 (1)(2) 的原因是因为, 每颗硬币用的 02/17 02:06
7F：→ LPH66 : (1)(2) 推论都是一样的 02/17 02:07
8F：→ alan23273850: 再次感谢大大，大大的阅读能力真的比我好上许多， 02/17 07:30
9F：→ alan23273850: 我後来发现自己难以看懂该证明是因为我原本是减法 02/17 07:30
10F：→ alan23273850: 思维，就是已取硬币扣掉目标还剩下多少，然後才继 02/17 07:30
11F：→ alan23273850: 续看能不能拿下一个硬币，但是这样会让每次迭代的 02/17 07:30
12F：→ alan23273850: 剩余值都不同，导致式子难以证明，如果改成加法思 02/17 07:30
13F：→ alan23273850: 维的话每次的目标值都固定是 S，相较起来就方便许 02/17 07:30
14F：→ alan23273850: 多，由此可见证明技巧的重要性啊！ 02/17 07:30
15F：→ alan23273850: 另外我在举例的时候有发现到这种例子难以举出，说 02/17 07:32
16F：→ alan23273850: 不定有兴趣的板友也可以想想看怎麽举出实例，或是 02/17 07:32
17F：→ alan23273850: 说明这种情况根本就不存在 02/17 07:32
18F：推 LPH66 : 符合证明的例子的话, 因为这证明不含最小性 02/17 13:08
19F：→ LPH66 : 因此举例时可不用纠结在最小, 只要关系符合就行了 02/17 13:09