用动态规划方法求解0／1背包问题时,将“用前i个物品来装容量是X的背包”的0／1背包问题记为 KNAP(1,i

Question

用动态规划方法求解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}

Answer 1

正确答案：C
解析：利用贪心法可以解决普通背包问题(即允许将物品的一部分装入背包)，此时使用“优先选取单位重量效益最大的物品”的量度标准可以获得问题最优解，但是贪心法不能用来求解 0/1背包问题。利用动态规划求解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)最优解的值为以上两种情况中效益值的更大者，即fi(X)=max{fi-1(X),fi-1(X-wi)+pi}。