資源描述：
《noi導(dǎo)刊 資源背包動態(tài)規(guī)劃》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、背包類動態(tài)規(guī)劃問題長沙市雅禮中學(xué)朱全民經(jīng)典的背包問題（01背包）有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車運(yùn)送的總價值最大？搜索法對于每種物品，要么裝上卡車，要么不裝，因此，N種物品的裝箱方案共有2N種。按每種物品進(jìn)行搜索，方法如下：對第i種物品進(jìn)行搜索如果所有的物品都搜索完，則更新最優(yōu)解如果當(dāng)前的估計(jì)達(dá)不到最優(yōu)解，則回溯如果第i種物品能放，則放，并標(biāo)記，否則選下一個物品清除標(biāo)記回溯動態(tài)規(guī)劃可以按每個物品進(jìn)行規(guī)劃，同樣每種物品有選和不選兩種選擇設(shè)F(i,
2、j)表示前i件物品載重為j的最大效益，則有1<=i<=N,0<=j<=N初值：F(0,j)=0F(N,M)即答案顯然時間復(fù)雜度為O(NM)主程序如下fori:=1tomdof[0,i]:=0;//初始化fori:=1tondof[i,0]:=0;fori:=1tondo//動態(tài)規(guī)劃，遞推求fforj:=1tomdobeginifj>=w[i]then//背包容量夠大f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])else//背包容量不足f[i,j]:=f[i-1,j];end;滿背包問題
3、（01背包）有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車開車正好裝滿時，運(yùn)送的總價值最大？若無法裝滿卡車，則輸出無解。動態(tài)規(guī)劃設(shè)F(i,j)表示前i件物品背包為j的最大效益，則有1<=i<=N,0<=j<=N初值：F(0,j)=0，F(xiàn)(1,j)=-∞F(N,M)即答案顯然時間復(fù)雜度為O(NM)帶條件的背包問題（1）有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;第i件物品可能帶0~2個附件；若裝載附件，必須裝載主件，反之沒有約束；現(xiàn)有一輛載重M公斤的
4、卡車;問選取裝載哪些物品，使得卡車運(yùn)送的總價值最大？分析假設(shè)只有主件的情況，顯然與經(jīng)典背包問題完全相同！現(xiàn)在每個物品有附件，我們可以分成4種方案僅裝載主件裝載主件+第1個附件裝載主件+第2個附件裝載主件+2個附件由于上述4種并列，這是幾種不同的決策同時規(guī)劃即可動態(tài)規(guī)劃設(shè)F(i,j)表示前i件物品背包為j的最優(yōu)解，則有，1<=i<=N,0<=j<=M時間復(fù)雜度O(NM)多層背包問題有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;現(xiàn)有一輛載重M公斤的卡車;第i件物品限制最多只能取Xi個；問選取裝載哪些物品，使得卡車運(yùn)
5、送的總價值最大？分析我們可以類似01背包問題，將第i種物品拆分成x[i]個，這樣每個物品只有1件了,如下圖:然后對所有的物品采用動態(tài)規(guī)劃即可。F(i,j)=max{f(i-1,j-k*w[i])+k*c[i]}0<=k*w[i]<=j完全背包問題有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;現(xiàn)有一輛載重M公斤的卡車;每次可以選取某種物品的任意多件裝載；問選取裝載哪些物品，使得卡車運(yùn)送的總價值最大？分析類似多層背包問題將每個物品展開成X[i]=m/w[i]個，然后對所有的物品采用動態(tài)規(guī)劃即可。若兩件物品i、j滿足
6、c[i]<=c[j]且w[i]>=w[j],則將物品i去掉,不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費(fèi)用高的j換成物美價廉的i,得到至少不會更差的方案。由于每種物品有選和不選兩種情況，可以將每種物品的2k個當(dāng)成一個整體考慮。這樣對于某種物品要選取多個，都可以由若干個2k個物品進(jìn)行組合(即2進(jìn)制數(shù))。例如第i種物品要選10個，則10=23+21。這樣第i種物品的個數(shù)為k=㏒2(m/wi)物品，是一個很大的改進(jìn)。進(jìn)一步,在計(jì)算k時,K=㏒2(j/wi),j為當(dāng)前背包剩余空間。進(jìn)一步fori:=1tondo//
7、動態(tài)規(guī)劃，遞推求fforj:=mdownto1dobeginifj>=w[i]then//背包容量夠大f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])else//背包容量不足f[i,j]:=f[i-1,j];end;在這里為了使得每個物品只取1個或不取,采用了每次取j都是與i-1進(jìn)行比較，實(shí)際上保存了每1步取不同j的值改進(jìn)程序事實(shí)上，我們只關(guān)心剩余背包的最大值，也就是僅僅關(guān)心f(j),因此，在對f(j)更新時，只要背包容量可以，那么可以反復(fù)更新。程序如下：fori:=1tondo//動態(tài)
8、規(guī)劃，遞推求fforj:=0tomdobeginifj>=w[i]then//背包容量夠大f[j]:=max(f[j-w[i]]+c[i],f[j])end;思考題1：機(jī)器分配M臺設(shè)備，分給N個公司。若公司i獲得j臺設(shè)備，則能產(chǎn)生Aij效益問如何分配設(shè)備使得總效益最大？M<=15，N<=10。分析用機(jī)器數(shù)來做狀態(tài)，數(shù)組f(i,j)
