2. 计算机
  3. 考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6，3，5，4，6}，求背包问题的最大装包价值。若此为0一1背包问题，分析该问题具有最优子结构，定义递归式为 其中c(i，j)表示i个物品、

考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6，3，5，4，6}，求背包问题的最大装包价值。若此为0一1背包问题，分析该问题具有最优子结构，定义递归式为 其中c(i，j)表示i个物品、

admin2019-07-12  75
问题 考虑一个背包问题，共有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)，算法的时间复杂度为(2)。
若此为部分背包问题，首先采用归并排序算法，根据物品的单位重量价值从大到小排序，然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量，则得到的最大装包价值为(3)，算法的时间复杂度为(4)。
(2)
选项 A、Θ(nW)
B、Θ(nlgn)
C、Θ(n2)
D、Θ(nlgnW)
答案A
解析
转载请注明原文地址:https://kaotiyun.com/show/F1CZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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