用动态规划方法求解0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为 KNAP(1,i,X),设fi(X)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得效益值分别为Wj和巧Pj(j=1~n)。则依次求解f0(X)、f1(X)、…、fn(X)的过程中使用的递推关系式为(58)。
A.fi(X)=min{fi-1(X),fi-1(X)+pi}
B.fi(X)=min{fi-1(X),fi-1(X-wi)+pi}
C.fi(X)=max{fi-1(X),fi-1(X-wi)+pi}
D.fi(X)=max{fi-1(X-wi),fi-1(X)+pi}
第1题:
OPT(i,w): 从1-i种物品中选择,放入容量为w的背包时的最大价值。这是()问题动态规划算法的递推函数。
A.0/1背包
B.恰好装满的0/1背包
C.完全0/1背包
D.多重0/1背包
第2题:
0-1背包问题:给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。用动态规划法编写算法和程序实现0-1背包问题。并给出如下测试用例的求解过程:有5件物品,重量分别为(3,2,1,4,5),价值分别为(25,20,15,40,50),背包容量w=6。
第3题:
背包问题,背包容量C=20 ,物品价值p =[4, 8,15, 1, 6,3], 物品重量w=[5, 3,2, 10, 4, 8], 如果是0-1背包问题,求装入背包的最大价值和相应装入物品。 (1)该问题最好使用()算法求解? A 动态规划算法 B 贪心算法 C 枚举算法 D 分治算法 (2)装入背包的最大价值是_____, (3)最大价值对应的物品编号为____、____、____、____。(从小到大)
第4题:
OPT(i,w): 从1-i个物品中选择,放入容量为w的背包时的最大价值。这是()问题动态规划算法的递推函数。
A.0/1背包
B.恰好装满的0/1背包
C.完全0/1背包
D.多重0/1背包
第5题:
关于背包问题,正确的是()
A.01背包用动态规划求解,部分背包用贪心算法求解
B.01背包用贪心算法求解,部分背包用动态规划求解
C.背包问题都用贪心算法求解
D.背包问题都用动态规划求解