知识卡片

问题卡 · 5626.g.1.a

换币贪心可行也未必最少

理解等级:中级

按剩余金额尽量选大面额可很快得到一个方案,但币种决定局部选择是否安全。[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. 可以保证找到最优解 :贪心算法在这种情况下往往是最优选择,因为它往往比回溯、动态规划