知识卡片
换币贪心可行也未必最少
按剩余金额尽量选大面额可很快得到一个方案,但币种决定局部选择是否安全。[1,20,50]凑60时,先选50再补十枚1共11枚,而三枚20只需3枚。
这一个反例足以否定任意币种都最优的主张。原书实现还需非空、正面值和有序输入,余额小于最小币时不能继续硬减;测试通过一组货币也不能证明所有金额都满足贪心选择性质。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
贪心算法无法保证找到全局最优解,并且有可能找到非常差的解。它更适合 用动态规划解决。 一般情况下,贪心算法的适用情况分以下两种。 1. 可以保证找到最优解 :贪心算法在这种情况下往往是最优选择,因为它往往比回溯、动态规划
参考来源
- 位置:《Hello 算法--Go版本》第15章《贪心》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/8.html;spine 7,归一字符[4412,4522))
- 结论依据:实际60和98反例及coins贪心代码,保留算法保证与实现边界。
- 原始内容:贪心算法无法保证找到全局最优解,并且有可能找到非常差的解。它更适合 用动态规划解决。 一般情况下,贪心算法的适用情况分以下两种。 1. 可以保证找到最优解 :贪心算法在这种情况下往往是最优选择,因为它往往比回溯、动态规划