第六講動(dòng)態(tài)規(guī)劃背包問題經(jīng)典的背包問題（01背包）有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？2動(dòng)態(tài)規(guī)劃可以按每個(gè)物品進(jìn)行規(guī)劃，同樣每種物品有選和不選兩種選擇設(shè)F(i,j)表示前i件物品載重為j的最大效益，則有1<=i<=N,0<=j<=N初值：F(0,j)=0F(N,M)即答案顯然時(shí)間復(fù)雜度為O(NM)3主程序如下fori:=1tomdof[0,i]:=0;//初始化fori:=1tondof[i,0]:=0;fori:=1tondo//動(dòng)態(tài)規(guī)劃，遞推求f forj:=1tomdo begin ifj>=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;4滿背包問題（01背包）有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車開車正好裝滿時(shí)，運(yùn)送的總價(jià)值最大？ 若無法裝滿卡車，則輸出無解。5動(dòng)態(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)即答案顯然時(shí)間復(fù)雜度為O(NM)6帶條件的背包問題（1）有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;第i件物品可能帶0~2個(gè)附件；若裝載附件，必須裝載主件，反之沒有約束；現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？7分析假設(shè)只有主件的情況，顯然與經(jīng)典背包問題完全相同！現(xiàn)在每個(gè)物品有附件，我們可以分成4種方案僅裝載主件裝載主件+第1個(gè)附件裝載主件+第2個(gè)附件裝載主件+2個(gè)附件由于上述4種并列，這是幾種不同的決策同時(shí)規(guī)劃即可8動(dòng)態(tài)規(guī)劃設(shè)F(i,j)表示前i件物品背包為j的最優(yōu)解，則有，1<=i<=N,0<=j<=M時(shí)間復(fù)雜度O(NM)9多層背包問題有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車;第i件物品限制最多只能取Xi個(gè)；問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？10分析我們可以類似01背包問題，將第i種物品拆分成x[i]個(gè)，這樣每個(gè)物品只有1件了,如下圖:然后對(duì)所有的物品采用動(dòng)態(tài)規(guī)劃即可。F(i,j)=max{f(i-1,j-k*w[i])+k*c[i]}0<=k*w[i]<=j11完全背包問題有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車;每次可以選取某種物品的任意多件裝載；問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？12分析類似多層背包問題將每個(gè)物品展開成X[i]=m/w[i]個(gè)，然后對(duì)所有的物品采用動(dòng)態(tài)規(guī)劃即可。若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j],則將物品i去掉,不用考慮。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將價(jià)值小費(fèi)用高的j換成物美價(jià)廉的i,得到至少不會(huì)更差的方案。由于每種物品有選和不選兩種情況，可以將每種物品的2k個(gè)當(dāng)成一個(gè)整體考慮。這樣對(duì)于某種物品要選取多個(gè)，都可以由若干個(gè)2k個(gè)物品進(jìn)行組合(即2進(jìn)制數(shù))。例如第i種物品要選10個(gè)，則10=23+21。這樣第i種物品的個(gè)數(shù)為k=㏒2(m/wi)物品，是一個(gè)很大的改進(jìn)。進(jìn)一步,在計(jì)算k時(shí),K=㏒2(j/wi),j為當(dāng)前背包剩余空間。13進(jìn)一步fori:=1tondo//動(dòng)態(tài)規(guī)劃，遞推求f forj:=mdownto1do begin ifj>=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;在這里為了使得每個(gè)物品只取1個(gè)或不取,采用了每次取j都是與i-1進(jìn)行比較，實(shí)際上保存了每1步取不同j的值14改進(jìn)程序事實(shí)上，我們只關(guān)心剩余背包的最大值，也就是僅僅關(guān)心f(j),因此，在對(duì)f(j)更新時(shí)，只要背包容量可以，那么可以反復(fù)更新。程序如下： fori:=1tondo//動(dòng)態(tài)規(guī)劃，遞推求f forj:=0tomdo begin ifj>=w[i]then//背包容量夠大 f[j]:=max(f[j-w[i]]+c[i],f[j]) end;15思考題1：機(jī)器分配M臺(tái)設(shè)備，分給N個(gè)公司。若公司i獲得j臺(tái)設(shè)備，則能產(chǎn)生Aij效益問如何分配設(shè)備使得總效益最大？M<=15，N<=10。16分析用機(jī)器數(shù)來做狀態(tài)，數(shù)組f(i,j)表示前i個(gè)公司分配j臺(tái)機(jī)器的最大盈利。則狀態(tài)轉(zhuǎn)移方程為:f(i,j)=Max{f[i-1，k]+a[i，j-j]}(1<=i<=N,1<=j<=M,0<=k<=j)初始值:f(0,0)=0時(shí)間復(fù)雜度O(N*M2)17思考題2：硬幣找零給定N枚硬幣給定T元錢用這N枚硬幣找這T元錢，使得剩下的錢最少。剩下錢數(shù)最少的找零方案中的所需的最少硬幣數(shù)。N<=500,T<=10000.18分析設(shè)F[i]表示需要找的錢數(shù)為i時(shí)所需要的最少錢幣數(shù)。顯然有：F[i]=Min{F[i-A[j]]+1}{i≤T，1≤j≤N}初始值：F[0]=0。A[j]表示其中第j種錢幣的面值。時(shí)間復(fù)雜度為O(N*T)。19思考題3：系統(tǒng)可靠性一個(gè)系統(tǒng)由若干部件串聯(lián)而成，只要有一個(gè)部件故障，系統(tǒng)就不能正常運(yùn)行，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件故障，備用件就自動(dòng)進(jìn)入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費(fèi)用也越大，那么在一定總費(fèi)用限制下，系統(tǒng)的最高可靠性等于多少？給定一些系統(tǒng)備用件的單價(jià)Ck，以及當(dāng)用Mk個(gè)此備用件時(shí)部件的正常工作概率Pk（Mk），總費(fèi)用上限C。求系統(tǒng)可能的最高可靠性。20樣例輸入文件格式：第一行：nC第二行：C1P1(0)P1(1)…P1(X1)（0<=X1<=[C/Ck]）

…第n行：CnPn(0)Pn(1)…Pn(Xn)（0<=Xn<=[C/Cn]）輸入：220 30.60.650.70.750.80.850.950.70.750.80.80.90.95輸出：0.637521分析設(shè)f(i,j)表示將j的資金用到前i項(xiàng)備用件中去的最大可靠性，則有F(i,j)=max{F(i-1,j–k*Cost[i])*P[i,k]}0<=i<=n,0<=j<=C,0<=k<jdivCost(i)初始：F(0,0)=0目標(biāo)：F(n,C)時(shí)間復(fù)雜度：O(k*n*C)，這里k是常數(shù)因子，與數(shù)據(jù)相關(guān)22思考題4：快餐問題套餐由由A個(gè)漢堡，B個(gè)薯?xiàng)l和C個(gè)飲料組成生產(chǎn)漢堡、薯?xiàng)l、飲料的時(shí)間為p1,p2,p3有N條流水線，N<=10，第i條流水線生產(chǎn)時(shí)間為Ti每條流水線都可生產(chǎn)漢堡、薯?xiàng)l和飲料每天漢堡、薯?xiàng)l和飲料個(gè)數(shù)不超過100如何安排生產(chǎn)使得生產(chǎn)套餐數(shù)量最多。23分析對(duì)于每條流水線，它的生產(chǎn)時(shí)間是一定的，我們?nèi)绻懒松a(chǎn)漢堡和薯?xiàng)l的個(gè)數(shù)，就很容易計(jì)算出生產(chǎn)飲料的個(gè)數(shù)。因此，假設(shè)第i條流水線生產(chǎn)了i’個(gè)漢堡，j’個(gè)薯?xiàng)l,那么還能生產(chǎn)飲料個(gè)數(shù)為： k’=(Ti-i’*p1-j’*p2)/p324動(dòng)態(tài)規(guī)劃設(shè)f(x,i,j)表示前x條流水線生產(chǎn)i個(gè)漢堡，j個(gè)薯?xiàng)l最多還能生產(chǎn)飲料個(gè)數(shù)。如果前x-1條流水線只要生產(chǎn)i’漢堡，j’個(gè)薯?xiàng)l，生產(chǎn)的飲料為f(x-1,i’,j’)因此有第x條流水線必須生產(chǎn)了i-i’個(gè)漢堡，j-j’個(gè)薯?xiàng)l，剩下的時(shí)間生產(chǎn)k個(gè)飲料。因?yàn)榍皒條流水線生產(chǎn)的飲料= 前x-1條流水線生產(chǎn)的飲料+第x條流水線生產(chǎn)的飲料所以有，f(x,i,j)=max{f(x-1,i’,j’)+k}25流水線資源分配圖26思考？f(x,i,j)=max{f(x-1,i’,j’)+k} 1<=x<=n<=10,0<=i’<=i<=100,0<=j’<=j<=100k可以實(shí)時(shí)求出時(shí)間復(fù)雜度為10*1002*1002=109顯然超時(shí)！27優(yōu)化求出最多可能生產(chǎn)多少套，減少不必要循環(huán)。淘汰一些沒有意義狀態(tài)，比如生產(chǎn)了過多第三種物質(zhì)，卻沒把前兩種生產(chǎn)滿。讓每條流水線大多數(shù)時(shí)間按成套時(shí)間生產(chǎn)，留下一些時(shí)間進(jìn)行動(dòng)態(tài)規(guī)劃，這樣將在動(dòng)態(tài)規(guī)劃時(shí)，極大地減少每種物品的產(chǎn)量從而極大地減少動(dòng)態(tài)規(guī)劃的狀態(tài)數(shù)。28說明利用前兩個(gè)優(yōu)化基本可以出解第3個(gè)優(yōu)