0-1背包问题的回溯算法所需的计算时间为(),用动态规划算法所需的计算时间为()。
第1题:
此题为判断题(对,错)。
第2题:
考虑一个背包问题,共有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)。 采用自底向上的动态规划方法求解,得到最大装包价值为(62),算法的时间复杂度为(63)。 若此为部分背包问题,首先采用归并排序算法,根据物品的单位重量价值从大到小排序,然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量,则得到的最大装包价值为(64),算法的时间复杂度为(65)。
A.11
B.14
C.15
D.16.67
第3题:
A.分支界限算法
B.动态规划算法
C.贪心算法
D.回溯算法
第4题:
下列哪一种算法是随机化算法()
第5题:
关于0-1背包问题以下描述正确的是()
第6题:
不能保证求得0-1背包问题的最优解。
A.分支限界法
B.贪心算法
C.回溯法
D.动态规划策略
第7题:
● (65) 不能保证求得0-1 背包问题的最优解。
(65)
A. 分支限界法
B. 贪心算法
C. 回溯法
D. 动态规划策略
第8题:
A.O(n2n)
B.O(nlogn)
C.O(2n)
D.O(n)
第9题:
对于0-1背包问题和背包问题的解法,下面()答案解释正确。
第10题:
用贪心算法设计0-1背包问题。要求:说明所使用的算法策略;写出算法实现的主要步骤;分析算法的时间。