清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的一般 特征。 对丁一个具体的问题,怎么知道是否可用贪心算 法解此问题,以及能否得到问题的最优解呢?这个问题 很难给予肯定的回答。 但是,从许多可以用贪心算法求解的问题中看到这类 问题一般具有2个重要的性质:贪心选择性质和最优子 结构性质
11 4.2 贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的一般 特征。 对于一个具体的问题，怎么知道是否可用贪心算 法解此问题，以及能否得到问题的最优解呢?这个问题 很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问题中看到这类 问题一般具有2个重要的性质：贪心选择性质和最优子 结构性质
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通 过一系列局部最优的选择,即贪心选择来达到。这是 贪心算法可行的第一个基本要素,也是贪心算法与动 态规划算法的主要区别 动态规划算法通常以自底向上的方式解各子问题,而 贪心算法则通常以自顶向下的方式进行,以迭代的方 式作出相继的贪心选择,每作一次贪心选择就将所求 问题简化为规模更小的子问题。 对于一个具体问题,要确定它是否具有贪心选择性质 必须证明每一步所作的贪心选择最终导致问题的整体 最优解。 12
12 4.2 贪心算法的基本要素 1.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通 过一系列局部最优的选择，即贪心选择来达到。这是 贪心算法可行的第一个基本要素，也是贪心算法与动 态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而 贪心算法则通常以自顶向下的方式进行，以迭代的方 式作出相继的贪心选择，每作一次贪心选择就将所求 问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质， 必须证明每一步所作的贪心选择最终导致问题的整体 最优解
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 2.最优子结构性质 当一个问题的最优解包含其子问题的最优解 时,称此问题具有最优子结构性质。问题的最 优子结构性质是该问题可用动态规划算法或贪 心算法求解的关键特征。 13
13 4.2 贪心算法的基本要素 2.最优子结构性质 当一个问题的最优解包含其子问题的最优解 时，称此问题具有最优子结构性质。问题的最 优子结构性质是该问题可用动态规划算法或贪 心算法求解的关键特征
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 3.贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构 性质,这是2类算法的一个共同点。但是,对于具有最 优子结构的问题应该选用贪心算法还是动态规划算法 求解?是否能用动态规划算法求解的问题也能用贪心算 法求解?下面研究2个经典的组合优化问题,并以此说 明贪心算法与动态规划算法的主要差别
14 4.2 贪心算法的基本要素 3.贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构 性质，这是2类算法的一个共同点。但是，对于具有最 优子结构的问题应该选用贪心算法还是动态规划算法 求解?是否能用动态规划算法求解的问题也能用贪心算 法求解?下面研究2个经典的组合优化问题，并以此说 明贪心算法与动态规划算法的主要差别
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.2贪心算法的基本要素 0-1背包问题: 给定n种物品和一个背包。物品的重量是Wi,其价 值为Vi,背包的容量为C。应如何选择装入背包的物品, 使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品识有2种选择,即装 入背包或不装入背包。不能将物品媵入背包多次,也不能只装 入部分的物 15
15 4.2 贪心算法的基本要素 • 0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价 值为Vi，背包的容量为C。应如何选择装入背包的物品， 使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装 入背包或不装入背包。不能将物品i装入背包多次，也不能只装 入部分的物品i