贪心方法最优解的证明

《贪心方法最优解的证明》由会员分享，可在线阅读，更多相关《贪心方法最优解的证明（7页珍藏版）》请在装配图网上搜索。

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

2、DDD Y-KNAPSACK 所生成的贪心解。 如果Xi = X2 =Xn = 1，则显然为 最优解，得证。 否贝则存在Y=(yi, y2,yn)是背包 问题的最优解，且有：n Wjyj = Mi =4Step 1找到X与丫第一个不等的元素 所在的位置k，并将yk替换为Xk12 k nXXiX2 Xk XnYyiy2 yk ynZZiZ2 Zk ZnXi = yi = Zi (i= Pk+i/Wk+i =Pn/Wn)n=x Piyi + Wk (Zk-yk) (Pk/Wk)i iWk+i (yk+i-Zk+i) (Pk/Wk)+Wn (yn-Zn) (Pk/Wk)nn=x Piyi + (Pk

3、/Wk)W k (Zk-yk)心一乙)i zii 二k iStep3分析上式：如果能证明 Zkyk，则 yk增加到Zk,那么必须从（yk+i,，yn） 中减去同样多的量，保证总容量仍然是M。从而有 Wk (Zk-yk) = WiW-Zi),即卩 Wk (Zk-yk)i 土十n二 Wi (yi - Zi )=0Step4证明 Zkyk，即:Xkyk由贪心解算法，X的序列形式如下：j是使得Xj 1的最小下标，0=Xj112 j-1 jj+1 nX1111Xj000Y111yk ynY21111ykyk+1 ynY31111Xj0ykynY1、Y2、Y3分别为j和k相对位置不 同的三种情况：1) kj ； Xk=1 ， Xky k， 0=y kyk得证。2) k=j;M=w 1X1 +Wj-iXj-i+WjXjM=W 1X1 +Wj-1Xj-1+Wjyj + +W nyn如果XjVyj贝，Wiyi M，不成立=1只有Xjyj成立3) kj ；则 Xk=0, yk=0, ykXk,因此,ykXkM=w 1X1 +Wj-iXj-i+WjXjM=w 1X1 +Wj-iXj-i+WjXj+Wkyk+WnX n同样；WiyiM，不成立，因此得证。i 4得证nnStep5 PiZi =、Pi%i吕yStep6将X与Z比较，如果不等，则找到 第一个不等的元素，继续代换，直到X与最 优解相等为止。