Chaer動態(tài)規(guī)劃習(xí)題

習(xí)題7.3:給出一個求解二項式系數(shù)Cnk的高效算法。你設(shè)計的算法的時間復(fù)雜度是什么？1111211331146410123n0123

n南京理工大學(xué)輸入：整數(shù)n，k輸出：二項式系數(shù)CnkIfk==0||n==kreturn1;fori←0tonC[i,0]←1C[i,i]←1endforfori←2tonforj←1toi-1C[i,j]←C[i-1,j-1]+C[i-1,j]endforendforReturnC[n,k]Θ(1)Θ(n)T(n)=Θ(n2)Ifi=nandj=kthenbreak不會影響時間復(fù)雜度南京理工大學(xué)C[1,1]=0M1C[1,2]=60(M1M2)C[1,3]=132(M1M2)M3C[1,4]=180(M1M2)(M3M4)C[1,5]=？C[2,2]=0M2C[2,3]=90(M2M3)C[2,4]=132M2(M3M4)C[2,5]=207M2((M3M4)M5)C[3,3]=0M3C[3,4]=72(M3M4)C[3,5]=132(M3M4)M5C[4,4]=0M4C[4,5]=120(M4M5)C[5,5]=0M5min習(xí)題7.9:(題略)南京理工大學(xué)可重復(fù)背包問題(7.27)給定n個物品{u1,u2,…,un}和一個背包，物品i

的重量為wi，價值為vi，已知背包的承重量為C,并且每個物品的個數(shù)沒有限制。問：在不撐破背包的條件下，選擇哪些物品裝入背包，得到的總價值最大？可重復(fù)背包問題的形式化描述：給定C>0,wi>0,vi>0,1≤i≤n,找出一個n元的向量(x1,x2,…,xn)，xi為非負(fù)整數(shù)，1≤i≤n,求如下優(yōu)化問題：南京理工大學(xué)0-1情形：設(shè)V[i,j]表示從前i個物品{u1,u2,…,ui}中取出一部分裝入承重量為j的背包所能取得的最大價值。那么，當(dāng)i=n,j=C時，V[n,C]就是原問題的解?！璾1u2ui-1uij?w1w2wi-1wiv1v2vi-1viwij-wi…u1u2ui-1w1w2wi-1v1v2vi-1V[i-1,j-wi]j…u1u2ui-1w1w2wi-1v1v2vi-1V[i-1,j]Case1:Case2:南京理工大學(xué)可重復(fù)情形：方法1：設(shè)V[i,j]表示從前i個物品{u1,u2,…,ui}中取出一部分裝入承重量為j的背包所能取得的最大價值。那么，當(dāng)i=n,j=C時，V[n,C]就是原問題的解。…u1u2ui-1uij?w1w2wi-1wiv1v2vi-1vik*wij-k*wi…u1u2ui-1w1w2wi-1v1v2vi-1V[i-1,j-k*wi]j…u1u2ui-1w1w2wi-1v1v2vi-1V[i-1,j]Case1:Case2:南京理工大學(xué)輸入：物品集合{u1,u2,…,un}，重量分別為w1,w2,…,wn，價值分別為v1,v2,…,vn,承重量為C的背包//物品可重復(fù)裝入輸出：背包所能裝物品的最大價值1.fori←0ton2.V[i,0]←03.endfor4.forj←0toC5.V[0,j]←06.endfor7.fori←1ton//前i個物品8.forj←1toC//承重量C與物品重量wi均為整數(shù)，故j為整數(shù)9.V[i,j]←V[i-1,j]ifwi≤jtemp=0fork←1toj/wiifV[i-1,j-k*wi]+k*vi>temptemp←V[i-1,j-k*wi]+k*vi

endifendforV[i,j]←max{V[i,j],temp}endifendforendfor14.returnV[n,C]南京理工大學(xué)可重復(fù)情形：方法2：設(shè)V[j]表示從n物品{u1,u2,…,un}中取出一部分裝入承重量為j的背包所能取得的最大價值。那么，當(dāng)j=C時，V[C]就是原問題的解?！璾1u2un-1unj?w1w2v1v2wn-1wnvn-1vn南京理工大學(xué)貨幣兌換問題(7.30)假設(shè)在一個貨幣系統(tǒng)中，共有n種硬幣，它們的面值分別為v1,v2,…,vn.并且v1=1為最小硬幣面值。現(xiàn)我們希望兌換價值為y的貨幣，要讓硬幣的數(shù)目最少。xi為非負(fù)整數(shù)南