推 alan23273850: 哇哇哇！謝謝大大，我好像懂ㄌ，立馬贈送１０００Ｐ 02/16 14:55
→ alan23273850: 非常感謝您拯救 God of Computer Science，看來小弟 02/16 14:55
→ alan23273850: 離 God 的距離還非常遙遠呢！ 02/16 14:55
※ 引述《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. 數學歸納法) 即可證明如果有個方法使用多個硬幣
則這些硬幣合成一個也是個方法
--
1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町
つぐみ 歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬
チサト 1998/06/18 守野くるみ 打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙
2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空
啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.72.196 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1613409169.A.5BD.html