利用贪心法求解0/1背包问题时， (26) 能够确保获得最优解。用动态规划方求解O/1背包问题时，将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1，i，X)设fi(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W和p(j=1～n)，则依次求解f0(X)，f1(X)，…，fn(X)的过程中使用的递推关系式为 (27) 。 （26）处填（）。
A: 优先选取重量最小的物品
B: 优先选取效益最大的物品
C: 优先选取单位重量效益最大的物品
D: 没有任何准则
A: 优先选取重量最小的物品
B: 优先选取效益最大的物品
C: 优先选取单位重量效益最大的物品
D: 没有任何准则
举一反三
- 利用贪心法求解0/1背包问题时， (26) 能够确保获得最优解。用动态规划方求解O/1背包问题时，将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1，i，X)设fi(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W和p(j=1～n)，则依次求解f0(X)，f1(X)，…，fn(X)的过程中使用的递推关系式为 (27) 。 （27）处填（）。 A: fi(X)=min{fi-1(X),fi-1(X)+Pi} B: fi(X)=max{fi-1(X),fi-1(X-Wi)+Pi} C: fi(X)=min{fi-1(X-Wi),fi-1(X-Wi)+pi) D: fi(X)=max{fi-1(x-Wi),fi-1(X)+Pi}
- 利用贪心法求解0-1背包问题时， (27) 能够确保获得最优解。用动态规划方法求解0-1背包问题时，将“用前i个物品来装容量是X的背包”的0-1背包问题记为KNAP(1，i，X)，设fi(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为Wj和pj(j=1～n)。则依次求解f0(X)4，f1(X)，…，fn(X)的过程中使用的递推关系式为 (28) 。 （28）处填（）。 A: fi(X)=min{fi-1(X)，fi-1(X)+pi} B: fi(X)=max{fi-1(X)，fi-1(X-Wi)+pi} C: fi(X)=min{fi-1(X-Wi)，fi-1(X-Wi)+pi} D: fi(X)=max{fi-1(X-Wi)，fi-1(X)+pi
- 求一般背包问题的最优解：n=3，背包容量M=60，各物品的产生的效益值(p1，p2，p3 )=(10，20，50)，各物品的重量为(w1，w2，w3)=(20，30，40)，（1）求解背包的最佳效益值及其相应各物品的 (x1，x2，x3)值。（其中0≤xi≤1）。（2）如果是0/1背包问题，怎样计算背包的最佳效益值？
- 背包问题 （1）求背包问题的最优解：n=3，背包容量M=6，各物品的产生的效益值(P1，P2，P3 )=(1，2，5)，各物品的重量为(W1，W2，W3)=(2，3，4)，运用贪心法求解背包的最佳效益值，及其相应各物品的 (X1，X2，X3)值。（其中02264Xi22641） （2）若解决0/1背包问题，可用哪些算法技术来求解？
- 0-1背包问题中，背包容量是9，5种物品的重量分别是：3 2 4 3 55种物品的价值分别是：4 5 8 5 7m[i][j]表示：背包容量为j,可选物品为i,i+1,...,n时0-1背包问题最优值如下。最优解向量为（）[img=554x273]17e441dfc172128.png[/img][/i] A: 1 0 1 01 B: 0 1 1 01 C: 1 0 1 1 0 D: 0 1 1 1 0