※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1613409169.A.5BD.html