2. 计算机
  3. 用动态规划方法求解0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为 KNAP(1,i,X)，设fi(X)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为Wj和巧Pj(j=1～n)。则依次求解f0

用动态规划方法求解0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为 KNAP(1,i,X)，设fi(X)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为Wj和巧Pj(j=1～n)。则依次求解f0

admin2010-01-23  45
问题 用动态规划方法求解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}
答案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}。
转载请注明原文地址:https://kaotiyun.com/show/8gxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)