答案及解析：[填空题]考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6,3，5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最

问题：

[填空题] 考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6,3，5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最优子结构，定义递归式为
中级软件设计师,历年真题,2016年上半年（上午）《软件设计师》真题

其中c（i，j）表示i个物品、容量为j的0-1背包问题的最大装包价值，最终要求解c（n,W）。
采用自底向上的动态规划方法求解，得到最大装包价值为（　　），算法的时间复杂度为（　　）。
若此为部分背包问题，首先采用归并排序算法，根据物品的单位重量价值从大到小排序，然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量，则得到的最大装包价值为（　　），算法的时间复杂度为（　　）。
问题1选项
A.11
B.14
C.15
D.16.67
问题2选项
A.Θ(nW)
B.Θ(nlgn)
C.Θ(n2)
D.Θ(nlgnW)
问题3选项
A.11
B.14
C.15
D.16.67
问题4选项
A.Θ(nW)
B.Θ(nlgn)
C.Θ(n2)
D.Θ(nlgnW)

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题