问题
单项选择题
用动态规划方法求解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）的过程中使用的递推关系式为（）。
A．fi(=min{fi-1(,fi-1(+pi}
B．fi(=min{fi-1(,fi-1(X-wi)+pi}
C．fi(=max{fi-1(,fi-1(X-wi)+pi}
D．fi(=max{fi-1(X-wi),fi-1(+pi}
答案
参考答案：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}。