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

看板Math作者alan23273850 (God of Computer Science)時間4年前 (2021/02/16 19:26)推噓2(2推 0噓 17→)

留言19則, 2人參與討論串3/3 (看更多)

※ 引述《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

→