Untitled

CLRS Greedy mindmap pdf

CLRS Greedy mindmap pdf

贪心算法

1. 确定问题的最优子结构性质
2. 将优化问题转化为作为一种选择，即贪心选择
3. 贪心选择后应只留下一个子问题，其他子问题均为空
4. 证明贪心选择的正确性，即本次贪心选择与剩余子问题的最优解可以构成愿问题的最优解

• 从25、10、5、1中选出6角5分，最优解为25→25→10→1 ✔︎
• 从3中硬币11、5、1中选出15分的最少硬币数 11→1→1→1→1 这不是问题的最优解，最优解应为5→5→5。 不满足上面的第4点，不具备贪心选择性质。

贪心算法 ← 贪心选择性质 （局部最优⇒ 全局最优）+ 最优子结构

动态规划 ← 最优子结构

贪心算法效率高，子问题不需要都计算。

动态规划方法应用面更广，只需要具有最优子结构性质。贪心算法额外需要贪心选择性质，而且选择性质证明困难。