贪心算法要素 最优子结构 当一个问题的最优解包含子问题的最优解时,称这 个问题具有最优子结构 贪心选择性 当一个问题的全局最优解可以通过局部最优解得到 称这个问题具有贪心选择性 口证明思路 假定首选元素不是贪心选择所要的元素,证明将首元 素替换成贪心选择所需元素,依然得到最优解 数学归纳法证明每一步均可通过贪心选择得到最优解贪心算法要素 ◼ 最优子结构  当一个问题的最优解包含子问题的最优解时，称这 个问题具有最优子结构 ◼ 贪心选择性  当一个问题的全局最优解可以通过局部最优解得到 ，称这个问题具有贪心选择性  证明思路： ➢ 假定首选元素不是贪心选择所要的元素，证明将首元 素替换成贪心选择所需元素，依然得到最优解 ➢ 数学归纳法证明每一步均可通过贪心选择得到最优解 4