Re: [其他] 一題 Codeforces 取硬幣演算法反例證明

[alan23273850 (God of Computer Science)]

※ 引述《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://www.ptt.cc/bbs/Math/M.1613474791.A.08C.html
→ alan23273850: 這篇和上一篇最大的增補主要是強調順序性，一定要
→ alan23273850: 前一顆硬幣維持相同的選擇之後我才能開始後面一顆的
→ alan23273850: 推導，不然我不放心
※ 編輯: alan23273850 (111.242.235.50 臺灣), 02/16/2021 19:32:04
推 LPH66       : 嗯, 順序性這個問題原題解裡沒有明提
→ LPH66       : 是在 (1)(2) 兩個理由裡隱含了這回事
→ LPH66       : 但題解強調 (1)(2) 的原因是因為, 每顆硬幣用的
→ LPH66       : (1)(2) 推論都是一樣的
→ alan23273850: 再次感謝大大，大大的閱讀能力真的比我好上許多，
→ alan23273850: 我後來發現自己難以看懂該證明是因為我原本是減法
→ alan23273850: 思維，就是已取硬幣扣掉目標還剩下多少，然後才繼
→ alan23273850: 續看能不能拿下一個硬幣，但是這樣會讓每次迭代的
→ alan23273850: 剩餘值都不同，導致式子難以證明，如果改成加法思
→ alan23273850: 維的話每次的目標值都固定是 S，相較起來就方便許
→ alan23273850: 多，由此可見證明技巧的重要性啊！
→ alan23273850: 另外我在舉例的時候有發現到這種例子難以舉出，說
→ alan23273850: 不定有興趣的板友也可以想想看怎麼舉出實例，或是
→ alan23273850: 說明這種情況根本就不存在
推 LPH66       : 符合證明的例子的話, 因為這證明不含最小性
→ LPH66       : 因此舉例時可不用糾結在最小, 只要關係符合就行了