2. 计算机
  3. 利用贪心法求解0/1背包问题时，(26)能够确保获得最优解。用动态规划方求解O/1背包问题时，将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1，i，X)设fi(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得

利用贪心法求解0/1背包问题时，(26)能够确保获得最优解。用动态规划方求解O/1背包问题时，将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1，i，X)设fi(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得

admin2019-03-11  81
问题 利用贪心法求解0/1背包问题时，(26)能够确保获得最优解。用动态规划方求解O/1背包问题时，将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1，i，X)设fi(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W和p(j=1～n)，则依次求解f0(X)，f1(X)，…，fn(X)的过程中使用的递推关系式为(27)。
选项 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}
答案B
解析 背包问题描述如下：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值和最大。0/1背包：对于每一种物品I装入背包只有一种选择，即要么装入要么不装入，不能装入多次或只装入部分。部分背包则是对于每一种物品I可以只装入部分。贪心法就是不求最优解，只求可行解的思想，只是局部最优，不考虑整体最优性。因此对于贪心法关键是贪心准则。对于0/1背包，贪心法之所以不一定得到最优解是因为它无法保证最终能将背包容量占满，背包空间的闲置使得背包所装物品的总价值降低了。动态规划法是将一个不容易解决的较大问题划分为若干个易于解决的小问题。
转载请注明原文地址:https://kaotiyun.com/show/tvRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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