贪心方法最优解的证明

《贪心方法最优解的证明》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、最优解的证明最优解的含义：在满足约束条件的情况下，可使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。1）最优解证明思路：l比较贪心解x与任一最优解yl若x与y不等，则寻找第一个不同元素的位置，假设为xil替换最优解y的元素yi为xi，得到新的最优解zl证明:z与y相比，目标函数值没有变化l反复以上这种代换，直到新产生的最优解与贪心解x相等，即贪心解即最优解2）定理3.1及其证明定理3.1如果p1/w1≥p2/w2≥…≥pn/wn,则算法GREEDY-KNAPSACK对于给定

2、的背包问题实例生成一个最优解。证明：设X=(x1,x2,…,xn)是GRDDDY-KNAPSACK所生成的贪心解。①如果x1=x2=…=xn=1，则显然为最优解，得证。②否则，则存在Y=(y1,y2,…,yn)是背包问题的最优解，且有：=MStep1找到X与Y第一个不等的元素所在的位置k，并将yk替换为xk12…k…nXx1x2…xk…xnYy1y2…yk…ynZz1z2…zk…znxi=yi=zi(i

3、zkpk+zk+1pk+1+…+znpn=y1p1+…+yk-1pk-1+zkpk+zk+1pk+1+…+znpn=y1p1+…+ynpn–(ykpk+…+ynpn)+zkpk+zk+1pk+1+…+znpn=+pk(zk-yk)–[pk+1(yk+1-zk+1)+...+pn(yn-zn)]=+wk(zk-yk)(pk/wk)–[wk+1(yk+1-zk+1)(pk+1/wk+1)+...+wn(yn-zn)(pn/wn)](pk/wk>=pk+1/wk+1>=…>=pn/wn)>=+wk(zk-yk)(pk/wk

4、)–[wk+1(yk+1-zk+1)(pk/wk)+...+wn(yn-zn)(pk/wk)]=+(pk/wk)[wk(zk-yk)–]Step3分析上式：如果能证明zk>yk，则yk增加到zk，那么必须从（yk+1，…，yn）中减去同样多的量，保证总容量仍然是M。从而有wk(zk-yk)=，即wk(zk-yk)–=0Step4证明zk>yk，即：xk>yk由贪心解算法，X的序列形式如下：j是使得xj<>1的最小下标，0<=xj<112…j-1jj+1…nX1111xj000Y111…yk…………ynY21111yk

5、yk+1…ynY31111xj0yk…ynY1、Y2、Y3分别为j和k相对位置不同的三种情况：1)kyk，0<=yk<=1因此xk>yk得证。2)k=j；M=w1x1+…+wj-1xj-1+wjxjM=w1x1+…+wj-1xj-1+wjyj+…+wnyn如果xjM，不成立只有xj>yj成立3)k>j；则xk=0，yk>=0，yk<>xk，因此，yk>xkM=w1x1+…+wj-1xj-1+wjxjM=w1x1+…+wj-1xj-1+wjxj+…wkyk+…+wnxn同样>M，不成立

6、，因此得证。Step5>=得证Step6将X与Z比较，如果不等，则找到第一个不等的元素，继续代换，直到X与最优解相等为止。