[其他] 一題 Codeforces 取硬幣演算法反例證明
看板Math作者alan23273850 (God of Computer Science)時間4年前 (2021/02/15 21:42)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/3 (看更多)
小弟今天正在練習這題 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. 其實解答和下面的討論區有附上證明，但是我看不懂！！所以想請問廣大資深鄉民
可否幫忙指點迷津，讓小弟我稍微參透一下他們的想法？
至於要怎麼找幣值我應該可以自己頓悟，所以這部分可以先不需要，感謝感謝！
--
推
11/27 18:45,
11/27 18:45
→
11/27 18:45,
11/27 18:45
→
11/27 18:45,
11/27 18:45
→
11/27 18:45,
11/27 18:45
→
11/27 18:45,
11/27 18:45
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.242.216.141 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1613396533.A.AA6.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：