专题讲座—贪心法.pdf

《专题讲座—贪心法.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南邮ACM协会贪心法贪心法————南邮ACM协会杨苜艺南邮ACM协会引例引例¢我们先看下面一个问题：假设在人民币的我们先看下面一个问题：假设在人民币的系统中（只考虑元的情况，即系统中（只考虑元的情况，即11，，22，，55，，1010，，2020，，5050，，100100），我们有各种面值的钱），我们有各种面值的钱币，且无数量限制，那么如果我们需要找币，且无数量限制，那么如果我们需要找出一个给定的钱币额，且要求使用的钱币出一个给定的钱币额，且要求使用的钱币尽可能的少，要如何设计算法？尽可能的少，要如何设计算法？南邮ACM协会¢按照我们的生活经验，对于

2、一个给定的币按照我们的生活经验，对于一个给定的币额，我们只需在所得系统中寻求一个小于额，我们只需在所得系统中寻求一个小于它的最大的钱币，然后给出这个钱币，再它的最大的钱币，然后给出这个钱币，再回溯到一个更小的问题就可以了。回溯到一个更小的问题就可以了。¢容易得到，这个算法就是在每个子问题中容易得到，这个算法就是在每个子问题中寻求一个最优的来完成达到总体的最优寻求一个最优的来完成达到总体的最优化，我们就把这种仅仅寻求局部最优解的化，我们就把这种仅仅寻求局部最优解的方法叫做贪心算法。方法叫做贪心算法。南邮ACM协会贪心算法的特点贪心算法的特点¢显然，如果一

3、道题目可以用贪心算法求显然，如果一道题目可以用贪心算法求解，那么，它的实现只是寻求一个局部最解，那么，它的实现只是寻求一个局部最优解，实现非常简单。优解，实现非常简单。¢再从时间复杂度上看，对于我们引例中的再从时间复杂度上看，对于我们引例中的问题，如果我们使用回溯法求解，它的复问题，如果我们使用回溯法求解，它的复杂度应该是杂度应该是OO（（N*N),N*N),而对于贪心算法，只而对于贪心算法，只需需O(N),O(N),且在空间复杂度上，也相对较小。且在空间复杂度上，也相对较小。¢这使我们完成程序的效率非常的高。这使我们完成程序的效率非常的高。南邮ACM

4、协会¢但但,,是否对求最优解的问题，都可以用贪心是否对求最优解的问题，都可以用贪心法来求解呢？法来求解呢？¢显然不是，对于我们引例中的问题，若我显然不是，对于我们引例中的问题，若我给出的面额为给出的面额为11，，55，，1111；如果我需要给出；如果我需要给出1515元，那么如果按照贪心算法，则是给出元，那么如果按照贪心算法，则是给出1111，，1*41*4，共，共55个，而显然，它的最优解应该是个，而显然，它的最优解应该是33个个55元的。元的。¢所以，我们就需要对问题进行考察，来判所以，我们就需要对问题进行考察，来判断是否可以贪心求解，即使认为可以

5、，如断是否可以贪心求解，即使认为可以，如何证明？何证明？南邮ACM协会贪心算法的基本要素贪心算法的基本要素¢贪心算法一般具有的两个重要特征贪心算法一般具有的两个重要特征¢一、贪心选择性质一、贪心选择性质¢所谓贪心选择性质是指所求问题的整体最所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，优解可以通过一系列局部最优解的选择，即贪心选择来达到。即贪心选择来达到。¢二、最优子结构性质二、最优子结构性质当一个问题的最优解当一个问题的最优解包含其子问题的最优解时，称此问题具有包含其子问题的最优解时，称此问题具有最优子结构。即当一个问题的局

6、部最优决最优子结构。即当一个问题的局部最优决定全局最优时。定全局最优时。南邮ACM协会我们来看下面两道题目对比一下我们来看下面两道题目对比一下¢一、一、00--11背包问题背包问题¢在在00--11背包问题中，需对容量背包问题中，需对容量为为cc的背包进行装的背包进行装载。从载。从nn个物品中选取装入背包的物品，每件物个物品中选取装入背包的物品，每件物品品ii的重量为的重量为w[i]w[i]，，价值为价值为v[i]v[i]。。对于可行的背包装对于可行的背包装载，背包中物品的总重量不能超过背包的容量，载，背包中物品的总重量不能超过背包的容量，最佳装载是指

7、所装入的物品价值最高。最佳装载是指所装入的物品价值最高。¢二、二、部分部分背包问题背包问题¢与与00--11背包类似，但不同的是，选择物品进入背包背包类似，但不同的是，选择物品进入背包时，可以选择物品的一部分而不是全部。时，可以选择物品的一部分而不是全部。南邮ACM协会¢这两个问题虽然相似，但背包问题可以用这两个问题虽然相似，但背包问题可以用贪心法求解，而贪心法求解，而00--11背包则不可以。背包则不可以。¢若用贪心法解决背包问题，我们的步骤是若用贪心法解决背包问题，我们的步骤是怎么样的？怎么样的？¢首先计算每种物品单位重量的价值，即首先计算每种物品

8、单位重量的价值，即v[i]/w[i],v[i]/w[i],，，然后进行贪心选择，将尽可能多然后