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  31
问题 考虑一个背包问题，共有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)。
(4)
选项 A、Θ(nW)
B、Θ(nlgn)
C、Θ(n2)
D、Θ(nlgnW)
答案B
解析 本题考查算法设计与分析的基础知识。
背包问题是一个经典的计算问题，有很多应用。背包问题有两类，0－1背包问题和部分背包问题。
若用c(i，j)表示i个物品、容量为j的最大装包价值，则0一1背包问题可以用动态规划方法求解，其递归式为：

根据该递归式，自底向上可以计算题干实例中各个子问题的最优解的值，如下表所示。

上表中行表示物品，列表示背包容量，每个元素的值表示，在仅考虑前i个物品时，背包容量为该列对应的值时，所获得的最大价值。
    根据上表的结果，得到最大价值为15。
    自底向上计算该递归式，在实现时其实是两重循环，物品个数的循环和背包容量的循环，因此时间复杂度为Θ(nW)。
    部分背包问题可以用贪心算法求解。首先根据物品的单位重量价值对物品并对其从大到小排序，然后依次取出物品放入背包，直到所有物品装完或者背包不能装入某个物品时，只放入该物品的一部分，让背包装满。单位重量价值如下表。

上表中行表示物品信息，即重量，价值和单位重量价值，列表示对应的物品。
    根据贪心策略，首先取出第一个物品放入背包，然后取出第二个物品和第五个物品放入背包，此时获得价值6+3+6=15，背包剩余容量10一2—2—4=8。此时不能将第三个物品全部放入背包，只能放2／6=1／3，对应获得的价值为5*1／3=1．67，因此得到所获得的最大价值为15+1．67=16．67。
若用时间复杂度为Θ(nlgn)的归并排序算法先对物品的单位重量价值排序，然后依次将物品放入背包(时间复杂度为Θ(n))，则整个算法的时间复杂度为Θ(nlgn)。
转载请注明原文地址:https://jikaoti.com/ti/JqG7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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