贪心专题.ppt

贪心思想专题范江文在近年来的信息学竞赛中,经常需要求一个问题的可行解和最优解,这就是所谓的最优化问题。贪心法是求解这类问题的一种常用算法。在众多的算法中,贪心法可以算得上是最接近人们日常思维的一种算法,他在各级各类信息学竞赛、尤其在一些数据规模很大的问题求解中发挥着越来越重要的作用。关于贪心什么是贪心? 贪心算法是指从问题的初始状态出发,通过若干次的局部贪心选择从而得出全局最优解或较优解的一种解题方法。事实上我们从“贪心”一词就可以看出来,贪心算法总是做出当前看来是最优的选择,也就是说贪心算法并不是从整体上加以考虑,它所做的选择只是在某种意义上的局部最优解,而许多问题本身的特性决定了该题运用贪心算法可以得到最优解或较有解。但是在很多的时候这种“局部最优”与“全局最优”往往又是矛盾的。初学的难点:1 算法需要构造 2 算法需要证明利用贪心解题所面临的问题一、确定问题是否适合用贪心算法求解? 二、如何选择贪婪的标准保证得到问题的最优解? 1、贪心选择性质:所求问题的整体最优解可以通过一系列局部最优的选择来达到,这样的选择称为贪心选择。这些选择只依赖于以往所做过的选择,决不依赖于将来的选择,从而使得算法在编码和执行的过程中都有一定的速度优势。 2、最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。下面通过一个例子来说明以上两个特征: 确定问题是否适合用贪心算法求解? 有一个 3*3的方格,每个格子有一个正整数,要求每行格子中取一个数,使得取出来的 3个数字之和最大。局部最优:从每行中取出最大的数全局最优:由局部最优取得的结果得到( 20+7+14 ) =》符合: 贪心选择性质三行的最优解: 20+7+14 前两行的最优解: 20+7 第一行的最优解: 20. 。。。。=> 符合: 最优子结构性质所以这道题首选贪心算法 12 14 3 576 8920 不符合贪心选择性质,因此这个问题不能再用贪心算法思考:这道题可以用什么方法来做? 依然用贪心得出的结果: 3+14+12+5+8=42 但是另外一条路径: 3+6+20+9+8=46 才是最优解,为什么贪心失灵了? 12 14 3 576 8920 如果将题目改为:从左下角出发,每次只能向上或想右移一个空格,现在要求找出一条路径使得从左下角到达右上角所经过的格子中的数字之和最大? 从3出发面临 6和14两个选择,贪心的做法是选择 14,从而使得错过了从 6继续前进的可能获得最优值的机会。最后使得“局部最优无法带来全局最优”。如何选择贪心标准? 【部分背包】给定一个最大载重量为 M的卡车和 N种食品,有食盐,白糖,大米等。已知第 i种食品的最多拥有 Wi 公斤,其商品价值为 Vi元/公斤,编程确定一个装货方案,使得装入卡车中的所有物品总价值最大。【分析】因为每一个物品都可以分割成单位块,单位块的利益越大显然总收益越大,所以它局部最优满足全局最优,可以用贪心算法解决。【方法】先将单位块收益按从大到小进行排列,然后用循环从单位块收益最大的取起,直到不能取为止便得到了最优解。?问题初始化; //读入数据?按 Vi从大到小将商品排序; ? I := 1; ? repeat ? if M = 0 then Break; // 如果卡车满载则跳出循环? M := M - Wi; ? if M >= 0 then 将第 I种商品全部装入卡车? else ?将M重量的物品 I装入卡车, M=0; ? I := I + 1; // 选择下一种商品? until (M <= 0) OR (I >N) 算法在解决上述问题的过程中,首先根据题设条件, 找到了贪心选择标准(Vi) ,并依据这个标准直接逐步去求最优解。【01背包】给定一个最大载重量为 M的卡车和 N种动物。已知第 i种动物的重量为 Wi ,其最大价值为 Vi,设定 M,Wi , Vi均为整数,编程确定一个装货方案,使得装入卡车中的所有动物总价值最大。【分析】本题与上题的最大区别是:各种动物不能宰了再装入卡车,也就是说本题中的物品是不可分割的。既然不可分割,就意味着卡车不一定能装满。(不一定装满就意味着往往不能用贪心算法) 例如:设 N=3 ,卡车最大载重量是 100 ,三种动物 A、B、C的重量分别是 40, 50,70,其对应的价值分别是 80、100 、150 。方法一:按贪心的思想,三种动物的单位价值 Vi/Wi 分别为 2,2, 。显然, 我们首先选择动物 C,得到价值 150 ,然后任意选择 A或B,由于卡车最大载重为100 ,因此卡车不能装载其他动物。方法二:直接选择 A和B两种动物都装进去,可获得价值为 80+100=18