作者alan23273850 (God of Computer Science)
看板Math
標題[其他] 一題 Codeforces 取硬幣演算法反例證明
時間Mon Feb 15 21:41:56 2021
小弟今天正在練習這題
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. 其實解答和下面的討論區有附上證明，但是我看不懂！！所以想請問廣大資深鄉民
可否幫忙指點迷津，讓小弟我稍微參透一下他們的想法？
至於要怎麼找幣值我應該可以自己頓悟，所以這部分可以先不需要，感謝感謝！
--
1F：推 FXW11314: 119學生：我讀頂大11/27 18:45
2F：→ FXW11314: 116學生：我讀四大11/27 18:45
3F：→ FXW11314: 114學生：我讀清交11/27 18:45
4F：→ FXW11314: 113學生：我讀交清11/27 18:45
5F：→ FXW11314: 112學生：我讀學店11/27 18:45
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.242.216.141 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1613396533.A.AA6.html