算法設(shè)計(jì)與分析 0.1背包問(wèn)題

0/1背包問(wèn)題本節(jié)將使用動(dòng)態(tài)規(guī)劃的由前向后處理方法（也稱(chēng)備忘錄算法）處理0/1背包問(wèn)題：s.t.（6.3.1）通過(guò)作出變量的取值序列來(lái)給出最優(yōu)解。這個(gè)取值序列的對(duì)應(yīng)決策序列是。在對(duì)作出決策之后，問(wèn)題處于下列兩種狀態(tài)之一：背包剩余的容量仍為，此時(shí)未產(chǎn)生任何效益；背包的剩余容量為，此時(shí)的效益值增長(zhǎng)了。因而(6.3.2)一般地，如果記0/1背包子問(wèn)題：s.t.(6.3.3)最優(yōu)解的值為，則有(6.3.4)這里，。為使(6.13)式能夠有效地遞推下去，需要延拓k和X的取值范圍：；補(bǔ)充定義：(6.3.5)事實(shí)上，我們的主要目的是計(jì)算出，根據(jù)(6.3.2)式，我們可能需要計(jì)算，而為了計(jì)算，可能需要計(jì)算，如此等等，在遞推公式(6.3.4)中用到的X值可能為負(fù)數(shù)。另外，如果將看作X的函數(shù)（稱(chēng)為第k個(gè)函數(shù)），則是一個(gè)分段函數(shù)，而且當(dāng)時(shí)取常值。所以將X的取值范圍延拓至全體實(shí)數(shù)。例子。由遞推式(6.3.5)，，而且當(dāng)時(shí)等式成立，這一事實(shí)可以寫(xiě)成上述諸函數(shù)具有如下性質(zhì)：1．每個(gè)階梯函數(shù)都是由其跳躍點(diǎn)偶決定的。如果有個(gè)跳躍點(diǎn):，各點(diǎn)的函數(shù)值分別是，則(6.3.6)這里約定。2．令Sk是階梯函數(shù)的跳躍點(diǎn)偶的集合，則階梯函數(shù)的跳躍點(diǎn)偶之集去掉點(diǎn)偶(0,0)后，恰是集合=(6.3.7)這是因?yàn)楹瘮?shù)的圖象恰是由函數(shù)的圖象先向右平移，然后再向上移動(dòng)而得。如前面例子m[1][X-w2]+p2332m[1][X]211bb012345601234567S1={(0,0),(2,1)}(w2,p2)=(3,2)S2a={(3,2),(5,3)}m[2][X]321S2={(0,0),(2,1),(3,2),(5,3)}01234567b根據(jù)遞推公式(6.13)，Sk是從Sk-1Ska中去掉那些點(diǎn)偶：在Sk-1Ska中存在點(diǎn)偶使得而且，此時(shí)我們說(shuō)淹沒(méi)。前面例子的諸Sk計(jì)算如下：在由、向的歸并過(guò)程中，(5,3)被(4,5)淹沒(méi)。3．在處理實(shí)際問(wèn)題時(shí)，由于要求，在計(jì)算時(shí)應(yīng)該去掉那些使得的跳躍點(diǎn)偶。根據(jù)前面的提到的淹沒(méi)規(guī)則，如果將中的元素按照第一個(gè)分量的遞增次序排列，則第二個(gè)分量也呈遞增的次序，而且的最后一個(gè)元素，設(shè)為，的值即是0/1背包問(wèn)題(6.3.1)的最優(yōu)值。4．最優(yōu)解的獲得可以通過(guò)檢查諸來(lái)確定。設(shè)是的最后一個(gè)元素。若，則.因?yàn)榇藭r(shí)函數(shù)和函數(shù)在Xc范圍內(nèi)的最大值一致，表明0/1背包問(wèn)題(6.3.1)與其子問(wèn)題s.t.(6.3.8)有相同的最優(yōu)值。若，則。因?yàn)?，此時(shí)函數(shù)在Xc范圍內(nèi)的最大值是函數(shù)的最大值加，相應(yīng)地，0/1背包問(wèn)題(6.3.1)的最優(yōu)值是其子問(wèn)題(6.3.8)的最優(yōu)值加。注意到此時(shí)跳躍點(diǎn)偶一定具有形式(6.3.9)其中。于是，我們可以依與否而決定取0或1。如此等等，我們可以逐一確定的值。在上述例子中，整理后的諸為：(6,6)是的最后一個(gè)跳躍點(diǎn)偶，所以該0/1問(wèn)題的最優(yōu)值是6。這個(gè)點(diǎn)偶不在中，因而;又，據(jù)此判斷的取值。因?yàn)椋?；最后由知，所以最?yōu)解為.為實(shí)現(xiàn)上述算法，可以用兩個(gè)一維數(shù)組B和V來(lái)存放所有的跳躍點(diǎn)偶(b,v)，跳躍點(diǎn)偶集互相鄰接地存放（將諸中的全部元素統(tǒng)一編號(hào)，從生成時(shí)，元素也是遞升地產(chǎn)生的，而且使用淹沒(méi)規(guī)則），并用指針F(k)來(lái)指示集合Sk，即Sk的第一個(gè)元素的位置，而F(n)-1是中最后一個(gè)元素的位置（這里不存放Sn是由于我們只需要它的最后一個(gè)元素，而這個(gè)元素或者是Sn-1的最后一個(gè)元素，此時(shí)Sn-1與Sn有相同的最后元素；或者具有形式(6.3.9)，而且是滿(mǎn)足的最大值。所以，確定Sn的最后元素不必將Sn的元素全部求出來(lái)。而且確定最優(yōu)解的其它變量時(shí)也不使用數(shù)據(jù)Sn）。因?yàn)楫a(chǎn)生Sk僅使用信息Sk-1和，所以不必存儲(chǔ)。根據(jù)以上分析，我們不難給出動(dòng)態(tài)規(guī)劃解0/1背包問(wèn)題的算法偽代碼。程序6-3-10/1背包問(wèn)題動(dòng)態(tài)規(guī)劃算法偽代碼DKnapsack(w,p,c,n,m)//數(shù)組w,p中的元素分別代表各件物品的//重量和價(jià)值，n是物品個(gè)數(shù)，c代表背包容量realp(n),w(n),B(m),V(m),ww,pp,c;integerF[0:n],l,h,i,j,p,next;F[0]=1;B[0]=V[0]=0;l=1;h=1;//S0的首和尾F(1)=2;next=2;//B、V中的第一個(gè)空位forifrom1ton-1dok=1;u=最大指標(biāo)r，使得1rh,而且B[r]+wic;forjfrom1toudo(ww,pp)=(B[r]+wi,V[r]+pi);//Sia中的下一個(gè)元素whilekh&&B[k]<wwdo//從Si-1中取來(lái)元素歸并B[next]=B[k];V[next]=V[k];Next=next+1;k=k+1;endwhileifkh&&B[k]=wwthenpp=max(V[k],pp);k=k+1;endififpp>V[next-1]then(B[next],V[next])=(ww,pp);next=next+1;endifwhilekh&&V[k]<V[next-1]do//清除k=k+1;endwhileendforwhilekhdo//將Si-1剩余的元素并入Si(B[next],V[next])=(B[k],V[k]);next=next+1;k=k+1;endwhilel=h+1;h=next-1;F(i+1)=next;//為Si+1賦初值endfortraceparts//逐一確定endDknapsack算法DKnapsack的主要工作是產(chǎn)生諸Si。在i>0的情況下，每個(gè)Si由Si-1和Sia歸并而成，并且|Sia||Si-1|。因此|Si|2|Si-1|，