為什麼這篇blog entry題目鄉民發文收入到精華區:因為在blog entry題目這個討論話題中,有許多相關的文章在討論,這篇最有參考價值!作者alan23273850 (God of Computer Science)看板Math標題[其...
小弟今天正在練習這題 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. 其實解答和下面的討論區有附上證明,但是我看不懂!!所以想請問廣大資深鄉民
可否幫忙指點迷津,讓小弟我稍微參透一下他們的想法?
至於要怎麼找幣值我應該可以自己頓悟,所以這部分可以先不需要,感謝感謝!
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.242.216.141 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1613396533.A.AA6.html