vlambda博客
学习文章列表

1.确定问题的最优子结构

2.设计一个递归算法（递归式等）

3.证明如果我们做出一个贪心选择，则只剩下一个子问题

4.证明贪心选择总是安全的（步骤3、4的顺序可以调换）

5.设计一个递归算法实现贪心策略

6.将递归算法转换为迭代算法

更一般地，我们可以按如下步骤设计贪心算法：

• 将最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解

• 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。

• 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

贪心选择性质和最优子结构是证明一个贪心算法是否能求解一个最优化问题的两个关键要素

贪心选择性质

1.做出局部最优（贪心）选择来构造全局最优解，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解

2.如果进行贪心选择时我们不得不考虑众多选择，通常意味着可以改进贪心选择，使其更为高效

最优子结构

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。此性质是能否应用动态规划和贪心方法的关键要素。

当应用于贪心算法时，我们通常使用更为直接的最优子结构。如前所述，我们可以假定，通过对原问题应用贪心选择即可得到子问题。我们真正要做的全部工作就是论证：将子问题的最优解与贪心选择组合在一起就能生成原问题的最优解，这种方法隐含地对子问题使用了数学归纳法，证明了在每个步骤进行贪心选择会生成原问题的最优解

0-1背包问题的贪心与动态规划差别

0-1背包问题是指：一个正在抢劫商店的小偷发现了n个商品，第i个商品价值vi美元，重wi磅，vi和wi都是整数。这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅重的商品，W是一个整数。他应该拿哪些商品呢？

(这个问题是0-1背包问题，因为对每个商品，小偷要么把它完整拿走，要么把它留下。他不能只拿走一个商品的一部分，或者把一个商品拿走多次)

分析：考虑重量不超过W而价值最高的装包方案。

• 商品1重10磅，价值60美元

• 商品2重20磅，价值100美元

• 商品3重30磅，价值120美元