貪心方法最優(yōu)解的證明

最優(yōu)解的證明最優(yōu)解的含義：在滿足約束條件的情況下，可使目標(biāo)函數(shù)取極（大或?。┲档目尚薪?。貪心解是可行解，故只需證明：貪心解可使目標(biāo)函數(shù)取得極值。1） 最優(yōu)解證明思路：?比較貪心解X與任一最優(yōu)解y?若X與y不等，則尋找第一個(gè)不同元素的位置，假設(shè)為X.I?替換最優(yōu)解y的元素y為X,?，得到新的最優(yōu)解z?證明:z與y相比，目標(biāo)函數(shù)值沒有變化?反復(fù)以上這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解工相等，即貪心解即最優(yōu)解2） 定理3.1及其證明定理3.1如果p1/w1Np2/w2N…Npn/wn，則算法GREEDY-KNAPSACK對(duì)于給定的背包問題實(shí)例生成一個(gè)最優(yōu)解。證明：設(shè)X=（x1,x2,…，xn）是GRDDDY-KNAPSACK所生成的貪心解。

如果x1=x2=…=xn=1,則顯然為最優(yōu)解，得證。否則，則存在Y=(y「y2,…,yn)是背包問題的最優(yōu)解，且有： n寸=M乙wJiii=112???12???k???nXx1x2???xk???xnYy】???yk???ynZZ1Z2???Zk???ZnStep1找到X與Y第一個(gè)不等的元素所在的位置k，并將yk替換為xkxi=yi=zi(i<k)；zk=xk；Step2計(jì)算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饑學(xué))(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)中減去同樣多的量，保證總?cè)萘咳匀皇荕。從而有wk(Zk-yp=孔(y_z)，即wk(Zk-ypiiii=k+1-&(y—z)=0iiii=k+1Step4證明zk>yk，即：xk>yk由貪心解算法，X的序列形式如下：j是使得xj<>1的最小下標(biāo)，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