知识卡片

普通读书笔记卡 · 5626.g

局部最优先得到可行方案

理解等级:中级

找零时优先选择不超过剩余金额的最大面额,再对余额重复,是一种局部选择策略。它避免在每一步比较所有完整方案,通常更容易组织计算。

原书当前货币例得到一个可行结果,不证明任何币种都能得到最少硬币数。贪心是否最优要由问题结构另行证明,后文会用换币反例说明这个边界。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      每一步都采取当前看来最好的选择(尽可能用大面额的货币) ,最终得到了可行的找零方 案。从数据结构与算法的角度看,这种方法本质上是“贪心”算法。 小到烹饪一道菜,大到星际航行,几乎所有问题的解决都离不开算法。计算机的出现使

    参考来源

    - 位置:《Hello 算法--Go版本》第01章《初识算法》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[15309,15419)) - 结论依据:找零例明确局部最大面额与可行解,保留最优性未证明的边界。 - 原始内容:每一步都采取当前看来最好的选择(尽可能用大面额的货币) ,最终得到了可行的找零方 案。从数据结构与算法的角度看,这种方法本质上是“贪心”算法。 小到烹饪一道菜,大到星际航行,几乎所有问题的解决都离不开算法。计算机的出现使