Open youngyangyang04 opened 3 months ago
贪carl的心❤️
贪心
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 例1:有一堆钞票可以拿走十张,如果想达到最大的金额要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。 例2:如果是有一堆盒子,背包体积为 n,如何把背包尽可能装满?如果还每次选最大的盒子就不行了,这时候就需要动态规划。
贪心的使用
贪心算法没有固定的套路。那如何验证能否用贪心呢?最好用的策略就是举反例,如果想不到反例,就试一试贪心吧。
https://www.programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html