作者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/cn.aspx?n=bbs/Math/M.1613396533.A.AA6.html