利用贪心法求解0／1背包问题时,(55)能够确保获得最优解。用动态规划方法求解 0／1背包问题时,将“用

Question

利用贪心法求解0/1背包问题时，(55)能够确保获得最优解。用动态规划方法求解 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)的过程中使用的递推关系式为(56)。.

A．优先选取重量最小的物品

B．优先选取效益最大的物品

C．优先选取单位重量效益最大的物品

D．没有任何准则

Answer 1

正确答案：D
解析：本题考查0/1背包问题的动态规划求解方法。
  利用贪心法可以解决普通背包问题(即允许将物品的一部分装入背包)，此时使用“优先选取单位重量效益最大的物品”的量度标准可以获得问题最优解，但是贪心法不能用来求解0/1背包问题，题目中供选择的A、B、C三种量度标准均不能确保获得最优解。
  利用动态规划求解0/1背包问题时，按照题目中约定的记号。KNAP(1,i,X)的最优解来自且仅来自于以下两种情况之一：
  . 第i个物品不装入背包，此时最优解的值就是子问题KNAP(1,i-1,X)的最优解的效益值，即为fi-1(X)；
  . 第i个物品装入背包，此时最优解的值为第i个物品的效益值与子问题 KNAP(1,i-1,X-wi)的最优解效益值之和，即为fi-1(X-wi)+pi。
  综上，KNAP(1,i,X)最优解的值为以上两种情况中效益值更大者，即取max。