Chaer动态规划习题

习题7.3:给出一个求解二项式系数Cnk的高效算法。你设计的算法的时间复杂度是什么？1111211331146410123n0123

n南京理工大学输入：整数n，k输出：二项式系数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不会影响时间复杂度南京理工大学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习题7.9:(题略)南京理工大学可重复背包问题(7.27)给定n个物品{u1,u2,…,un}和一个背包，物品i

的重量为wi，价值为vi，已知背包的承重量为C,并且每个物品的个数没有限制。问：在不撑破背包的条件下，选择哪些物品装入背包，得到的总价值最大？可重复背包问题的形式化描述：给定C>0,wi>0,vi>0,1≤i≤n,找出一个n元的向量(x1,x2,…,xn)，xi为非负整数，1≤i≤n,求如下优化问题：南京理工大学0-1情形：设V[i,j]表示从前i个物品{u1,u2,…,ui}中取出一部分装入承重量为j的背包所能取得的最大价值。那么，当i=n,j=C时，V[n,C]就是原问题的解。…u1u2ui-1uij?w1w2wi-1wiv1v2vi-1viwij-wi…u1u2ui-1w1w2wi-1v1v2vi-1V[i-1,j-wi]j…u1u2ui-1w1w2wi-1v1v2vi-1V[i-1,j]Case1:Case2:南京理工大学可重复情形：方法1：设V[i,j]表示从前i个物品{u1,u2,…,ui}中取出一部分装入承重量为j的背包所能取得的最大价值。那么，当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:南京理工大学输入：物品集合{u1,u2,…,un}，重量分别为w1,w2,…,wn，价值分别为v1,v2,…,vn,承重量为C的背包//物品可重复装入输出：背包所能装物品的最大价值1.fori←0ton2.V[i,0]←03.endfor4.forj←0toC5.V[0,j]←06.endfor7.fori←1ton//前i个物品8.forj←1toC//承重量C与物品重量wi均为整数，故j为整数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]南京理工大学可重复情形：方法2：设V[j]表示从n物品{u1,u2,…,un}中取出一部分装入承重量为j的背包所能取得的最大价值。那么，当j=C时，V[C]就是原问题的解。…u1u2un-1unj?w1w2v1v2wn-1wnvn-1vn南京理工大学货币兑换问题(7.30)假设在一个货币系统中，共有n种硬币，它们的面值分别为v1,v2,…,vn.并且v1=1为最小硬币面值。现我们希望兑换价值为y的货币，要让硬币的数目最少。xi为非负整数南