资源描述：
《四、贪心算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2．3贪心法(GreedyApproach)一、基本思想适用问题：组合优化问题，适合优化原则。设计方法：多步判断。在每步判断时在满足约束条件的情况下根据某个局部的优化测度(可能是目标函数,也可能不是)考虑部分解中一个变量的选择。使用贪心法要解决的问题:是否可以得到最优解?不能得到最优解,解与最优解的误差估计。例1活动选择问题S={1,2,…,n}为n项活动的集合。si,fi分别为活动i的开始和结束时间。活动i与j相容当且仅当si≥fj,或fi≥sj,求最大的两两相容的活动集。解：按照结束时间的递增顺序将活
2、动排列为1,2,…,n,使得f1≤f2≤…≤fn算法GreedySelect1.n←length[S];2.A←{1};3.j←1;4.fori←2ton5.doifsi≥fj6.thenA←A∪{i};7.j←i;8.returnA.最后完成时间为max{fk:k∈A}.例如下述输入I1234567891011si130535688212fi4567891011121314解为A={1,4,8,11}t=14下面证明贪心法得到最优解。定理1算法Select执行到第k步,选择k项活动i1=1,i2,…,i
3、k,那么存在最优解A包含i1=1,i2,…,ik证明：对k归纳。k=1,设S={1,2,…,n}是活动集，活动按截止时间递增顺序排序，则存在最优解含有活动1。任取最优解A,A中的活动按照截止时间递增的顺序排列。如果A的第一个活动为j，j≠1,令A’=(A−{j})∪{1},由于f1≤fj,A’也是最优解，且含有1.假设命题对k为真。算法执行到第k步,选择了活动i1=1,i2,…,ik,根据归纳假设存在最优解A包含i1=1,i2,…,ik,A中剩下的活动选自集合S’={i
4、i∈S,si≥fk}。且B=A-{
5、i1,i2,…,ik}是S’的最优解。若不然，S’的最优解为B’，B’的活动比B多，那么B’∪{1,i2,…,ik}是S的最优解，且比A的活动多，与A的最优性矛盾。根据归纳基础，存在S’的最优解B含有S’中的第一个活动，设为ik+1,则{i,i,...,i}∪B={i,i,...i,i}∪(B−{i})12k12kk+1k+1包含了算法k+1步的选择，也是原问题的最优解，命题对k+1为真。二、贪心算法的设计：1.贪心算法的设计要素z适用于满足优化原则的组合优化问题，将问题表示成多步判断。整个判断序列对应问
6、题的最优解；而它的子序列对应子问题的最优解。z确定一个优化测度（不考虑以前各步的选择，只与当前状态有关），以优化测度的极大(或极小)作为贪心选择的依据z确定是否满足贪心选择性质——每步贪心选择都导致最优解。一般采用归纳法加以证明z自顶向下计算，通过贪心选择，将原问题规约为子问题。动态规划和贪心法比较：性质动态规划贪心法适用问题组合优化组合优化求解过程多步判断多步判断使用条件优化原则优化原则解的性质最优解有贪心选择性质下得到最优解否则为近似解求解关键列递推方程贪心选择性质的证明子问题形成先解子问题然后选择先
7、选择然后构成子问题求解顺序自底向上自顶向下数据结构数值表记录优化函数值无特殊要求标记表记录子问题划分时间复杂性依赖子问题重叠程度不高空间复杂性高不高2．贪心算法的正确性证明不是所有优化问题都具有贪心选择性质，证明贪心选择性质的方法---数学归纳法，可以对算法步数或问题规模进行归纳。例2部分装入背包问题(FractionalKnapsackProblem)一个旅行者准备随身携带一个背包.可以放入背包的物品有n个,每个物品的重量和价值分别为wj,vj.j=1,2,…,n,旅行者可以选择物品i的全部，也可以选择
8、物品i的xi部分，0≤xi≤1。如果背包的最大重量限制是c,怎样选择放入背包的物品以使得背包的价值最大?输入：c>0,wi>0,vi>0,i=1,…n.输出：nmax∑vixii=1n∑wixi≤ci=10≤x≤1i=1,2,...,ni设计贪心法如下：按照单位重量的价值从高到低对物品排序，尽量装入单位重量价值最高的物品，直到不能装入一个整物品为止，最后根据背包重量极限装入部分物品。通过对步数归纳可以证明部分装入背包问题满足贪心选择性质，且时间为T(n)=O(nlogn)。一般背包
9、问题不具有贪心选择性质，不能使用贪心法，因为对于某些输入不能得到最优解。0-1背包问题也不具有贪心选择性质。下面是0-1背包问题的描述。nmax∑vixii=1n∑wixi≤ci=1x=0,1,i=1,2,...,ni例3最优装载n个集装箱1,2,…,n装上轮船，集装箱i的重量wi,轮船装载重量限制为c，无体积限制。问如何装使得上船的集装箱最多？不妨设wi≤c.nmax∑xii=1n∑wixi≤ci=1x=0,1i=1,2,.
