软题库 培训课程
当前位置:信管网 >> 在线考试中心 >> 软件设计师题库 >> 试题查看
试卷年份2005年下半年
试题题型【单选题】
试题内容

利用贪心法求解0/1背包问题时,(1)能够确保获得最优解。用动态规划方法求解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) 的过程中使用的递推关系式为(2) 。
(1)A、优先选取重量最小的物品
B、优先选取效益最大的物品
C、优先选取单位重量效益最大的物品
D、没有任何准则
(2)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}

查看答案

相关试题