贪心方法最优解的证明

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

如果x1=x2=…=xn=1,则显然为最优解，得证。否则，则存在Y=(y「y2,…,yn)是背包问题的最优解，且有： n寸=M乙wJiii=112•••12•••k•••nXx1x2•••xk•••xnYy】•••yk•••ynZZ1Z2•••Zk•••ZnStep1找到X与Y第一个不等的元素所在的位置k，并将yk替换为xkxi=yi=zi(i<k)；zk=xk；Step2计算Z的效益值，需要证明Z的效益值大于等于Y的效益值pziii=1=Z1P1+…+zk-R-1+ZkPk+Zk+1Pk+1+-+ZnPn=y】P1+…+yk-1Pk-1+ZkPk+Zk+1Pk+1+…+ZnPn=y】P1+…+YnPn-％Pk+…+ynPn)+ZkPk+Zk+1Pk+1+・.・+ZnPn=E”+Pk(Zk-yp-ii=1庇+1佻+1-4+1)+“・+Pn(yn-Zn)]=&y+wk(Zk-yk)(Pk/wk)-iii=1[wk+1仇+1-如(Pk+1/wk+1)+..・+Wn饥学)(Pn/wn)](Pk/wk>=Pk+1/wk+1>=••>=Pn/wn)>=I”+wk(Zk-yJ(Pk/wP-iii=1[wk+1(yk+1-Zk+1)(Pk/wk)+...+wn(yn-Zn)叩』=&y+(Pk/wk)[wk(Zk-yk)—孔("Z)]iiii=1 i=k+1Step3分析上式：如果能证明Zk>yk，则yk增加到Zk，那么必须从(yk+1，…，yn)中减去同样多的量，保证总容量仍然是M。从而有wk(Zk-yp=孔(y_z)，即wk(Zk-ypiiii=k+1-&(y—z)=0iiii=k+1Step4证明zk>yk，即：xk>yk由贪心解算法，X的序列形式如下：j是使得xj<>1的最小下标，0<=xj<112•••j-1•JJ+1•••nX1111x.j000Y111••••••••••••ynY21111ykyk+1•••ynY31111x.J0yk…ynY1、Y2、Y3分别【为j和k相，，位置不同的三种情况：k<j；xk=1，xk<>yk，0<=yk<=1因此xk>yk得证。k=j；M=w1x1+_+w.六1+w.xjM=w1x1+_+w.六1+Wjyj+，.・+wnyn如果xj<yj则［>"不成立i=1只有xj>y.成立k>j；则xk=0，yk>=0，yk<>xk，因此，yk>xkM=w1x1+_+w.1Xj1+WjXjM=w1x1+_+w.六1+WjXj+...wkyk+..・+WX同样Xwy>M，不成立，因此得证。iii=1