对于表6—1的实例,若采用穷举法搜索整个解空间,则搜索树的结点数为 (7) ,而用了上述回溯法,搜索树的结点数为 (8) .
第1题
【问题2】(7分)
考虑表4-1的实例,假设有3个物品,背包容量为22。图4-1中是根据上述算法构造的搜索树,其中结点的编号表示了搜索树生成的顺序,边上的数字1/0分别表示选择/不选择对应物品。除了根结点之外,每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值,右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解,应该选择物品 (5) ,获得的价值为 (6) 。
对于表4-1的实例,若采用穷举法搜索整个解空间,则搜索树的结点数为 (7) ,而用了上述回溯法,搜索树的结点数为 (8) 。
第9题
其中c(i,j)表示i个物品、容量为j的0-1背包问题的最大装包价值,最终要求解c(n,W)。 采用自底向上的动态规划方法求解,得到最大装包价值为(62),算法的时间复杂度为(63)。 若此为部分背包问题,首先采用归并排序算法,根据物品的单位重量价值从大到小排序,然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量,则得到的最大装包价值为(64),算法的时间复杂度为(65)。
A.11
B.14
C.15
D.16.67
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!