贪心算法.ppt

贪心算法
贪心方法的基本思想
贪心是一种解题策略,也是一种解题思想
使用贪心方法需要注意局部最优与全局最优的关系,选择当前状态的局部最优并不一定能推导出问题的全局最优
利用贪心策略解题,需要解决两个问题:
该题是否适合于用贪心策略求解
如何选择贪心标准,以得到问题的最优解
【引例】在一个N×M的方格阵中,每一格子赋予一个数(即为权),规定每次移动时只能向上或向右。现试找出一条路径,使其从左下角至右上角所经过的权之和最大。
我们以2×3的矩阵为例:
若按贪心策略求解,所得路径为:1→3→4→6;
若按动态规划求解,所得路径为:1→2→10→6。
贪心法的特点
:算法中每一步选择都是当前看似最佳的选择,这种选择依赖于已做出的选择,但不依赖于未做的选择。
:算法中每一次都取得了最优解(即局部最优解),要保证最后的结果最优,则必须满足全局最优解包含局部最优解。
但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的,需要使用更理性的方法——动态规划(例如“0-1背包问题”与“部分背包问题”)
【问题1】部分背包问题
给定一个最大载重量为M的卡车和N种食品,有食盐,白糖,大米等。已知第i种食品的最多拥有Wi公斤,其商品价值为Vi元/公斤,编程确定一个装货方案,使得装入卡车中的所有物品总价值最大。
【分析】因为每一个物品都可以分割成单位块,单位块的利益越大,显然总收益越大,所以它局部最优满足全局最优,可以用贪心法解答。
方法如下:先将单位块收益按从大到小进行排列,然后用循环从单位块收益最大的取起,直到不能取为止便得到了最优解。
【问题2】0/1背包问题
给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi,其最大价值为Vi,设定M,Wi,Vi均为整数,编程确定一个装货方案,使得装入卡车中的所有动物总价值最大。
【分析】按贪心法:每次选价格最大的装载。很明显有反例:设N=3,卡车最大载重量是100,三种动物A、B、C的重量分别是40,50,70,其对应的总价值分别是80、100、150。
贪心策略与其他算法的区别
:与递推不同的是,贪心法中推进的每一步不是依据某一固定的递推式,而是当前看似最佳的贪心决策,不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略,是正确解决贪心问题的关键。
:与动态规划不同的是,贪心是鼠目寸光;动态规划是统揽全局。
几个简单的贪心例子
贪心策略
例题1:删数问题
键盘输入一个高精度的正整数n(n<=240位),去掉其中任意s个数字后剩下的数字按照原来的次序将组成一个新的正整数。编程对给定的n和s,寻求一种方案,使得剩下组成的新数最小。
【样例输入】
178543
4
【样例输出】13