2. 从业资格
  3. 考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：

考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：

题库2022-08-02  99
问题 考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6,3，5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最优子结构，定义递归式为其中c（i，j）表示i个物品、容量为j的0-1背包问题的最大装包价值，最终要求解c（n,W）。采用自底向上的动态规划方法求解，得到最大装包价值为（　　），算法的时间复杂度为（　　）。若此为部分背包问题，首先采用归并排序算法，根据物品的单位重量价值从大到小排序，然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量，则得到的最大装包价值为（　　），算法的时间复杂度为（　　）。问题1选项A.11B.14C.15D.16.67问题2选项A.Θ(nW)B.Θ(nlgn)C.Θ(n2)D.Θ(nlgnW)问题3选项A.11B.14C.15D.16.67问题4选项A.Θ(nW)B.Θ(nlgn)C.Θ(n2)D.Θ(nlgnW)
选项
答案 CADB
解析 这是典型的01背包问题，动态规划算法中，自底向上（递推）：从小范围递推计算到大范围，可以看到装第一个和第五个物品价值是最高的，这时候V=12了，然后占了6的重量了，只能装物品2了，价值15。
而此时的算法过程是对物品n和背包容量W分别进行比较以找到最优结果，因此时间复杂度为Θ(nW)。
空（3）（4）是部分背包，部分背包的时候计算每个物品单位重量价值多少，单位重量v={3 1.5 5/6 0.8 1.5},可以看到1 2 5的单位价值最高，选择125后背包重量还只有8，还有2个重量可以选择3得等5/3的价值，就是1.67，所以第三问为16.67。
再来看时间复杂度，本题先进行归并排序，然后再根据有序序列来选择放入背包的物品，因此算法分两部分，首先是归并排序时间复杂度为Θ(nlgn)，然后是放背包，因为已经排过序，所以只需要线性处理即可，此时时间复杂度为Θ(n)，综合起来，由于Θ(nlgn)>Θ(n)，因此整体时间复杂度为Θ(nlgn)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410389.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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