第2章 贪心算法.pptVIP

第 2 章 贪心算法 2.1 概述 2.1.1、贪心算法基本思想： 从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策,尽可能地求得当前最优的解； 当达到算法中某一步不需要再继续前进时，算法停止。 贪婪算法原理是通过局部最优来达到全局最优,采用逐步构造最优解的方法。在每个阶段，都做出一个看上去最优的决策（贪心选择），决策一旦做出，就不可再更改。 例：找零问题：（购物时怎么使找回零钱数最少） 首先，从最大币值开始；（贪心选择） 直到余额小于大币值才会选择较小币值； 如：找零107元 100元 1张 ； 50元 0张； 10元 0张； 5元 1张； 1元 2张； 2.1.2、贪心算法的基本要素： 何时可以采用贪心算法求解问题？ 如果一个问题具有以下2个性质，那么可以使用贪心算法来对其求解！ 1）最优子结构 最优子结构：当一个问题的最优解一定包含其子问题的最优解时，称此问题具有最优子结构。 即，一个问题的最优解能够分解成各个子问题来解决，通过子问题最优解能推到原问题最优解。 因为，贪心算法解题是依序研究每个子问题，最后综合得出结果. 2）贪心选择性 贪心选择:问题的整体最优解可以通过一系列局部最优的选择获得; 即,通过一系列的逐步贪心选择使得最终的选择方案是全局最优; 2.1.3、贪心算法的解题步骤与基本框架： 利用贪心算法求解问题通常包含3个步骤： 1）分解：将原问题分解成若干独立的阶段； 2）贪心选择：对于每个阶段根据贪心策略，进行贪心 选择； 3）合并：将各个阶段的解合并为原问题的解； 算法的基本框架： 从问题的某一初始解出发； while（能朝给定总目标前进一步） //贪心选择 利用可行的决策，求当前最优的一个解元素; 由所有解元素组合成问题的一个可行解。 补充1、找零问题 1、问题提出 某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱, 且取款的张数最少，统计所需各种币值(100,50,20,10,5,2,1元共七种)的张数。 2、解题思路： 1) 对每一个人的工资，用“贪婪”的思想，先尽量多地取大面额的币种，由大面额到小面额币种逐渐发放。 2) 利用数组应用技巧,将七种币值存储在数组B[ ]。七种币值就可表示为B[ i ] ,i=1,2,3,4,5,6,7。为了能实现贪婪策略，七种币应该从大面额的币种到小面额的币种依次存储。 3) 利用数组技巧,设置一个有7个元素的累加器数组S[ ] ; S[ i]存放对应i币种张数。 补充1、找零问题 3、算法描述： void greedy_zhaoling ( float GZ, int B[ ], int S[ ] ) //GZ应发工资 { for( j=1, j=7;j++) //贪心选择，依次给最大币种 { S[ j]=0； //初始化S[ j] A=GZ/B[ j]; //A表示对应j币种张数 S[ j]=S[ j ]+A; //S[ j]存放对应j币种总张数 GZ=GZ-A*B[ j]; } //每求出一种面额所需的张数后， 一定要把这部分金额减去： for(i=1;i=7;i++) print( B[ i], “----”, S[ i]); //输出币种和对应张数 } 4、算法分析 该算法的时间复杂度为O(c) 补充2、背包问题(普通背包问题) 1、问题提出 已知n个物体重量为：w1、w2… n个物体价值为：p1、p2… 背包载重为：M 两类背包问题： ①普通背包问题（贪心算法求解） 物体i可以部分的装入背包，若物体i的一部分xi装入背包，则装入的重量为wi*xi，装入的价值为pi*xi； ②0－1背包问题（不能用贪心算法求得最优解） 每一件物体不能分割，要么全部放入，要么全部不放入，称为0－1背包问题； 补充2、背包问题(普通背包问题) 2、算法基本思路 首先，按单位物品价值递增将物品排序； 然后，依次将单位价值大的物品放入背包（贪心选择），直到背包放满位置； 如果正在考虑装入的物品不能全部放进去，则可以将部分物品放入