下载APP
【多选题】
优先队列式分支限界法解决0-1背包问题时,下面描述正确的是
A.
右孩子结点的优先级等于父结点的优先级
B.
左孩子结点相应的背包内物品的价值等于父结点相应的背包内的物品价值
C.
右孩子结点相应的背包内物品的价值等于父结点相应的背包内的物品价值
D.
左孩子结点的优先级等于父结点的优先级
举报
题目标签:
分支限界法
优先队列
背包问题
参考答案:
参考解析:
刷刷题刷刷变学霸
举一反三
【单选题】0-1背包问题的回溯算法,下面的解释不正确的是
A.
解空间树是子集树
B.
左(1)分支的剪枝:当选择装入背包的物品重量之和超过背包容量时就剪枝。
C.
右(0)分支的剪枝:已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值(物品可分割,即用背包问题的贪心算法求得的最大价值)>当前最优值bestp, 就剪枝.
D.
当搜索至叶子结点时,一定是发现了到目前为止最好的解
查看完整题目与答案
【单选题】对于0-1背包问题和背包问题的解法,( )解释正确。
A.
都可用贪心算法求解
B.
0-1背包问题可用贪心算法求解,背包问题不能用贪心算法求解
C.
0-1背包问题可用动态规划或搜索算法求解,背包问题可用贪心算法求解
D.
因为0-1背包问题不具有最优子结构性质,所以不能用贪心算法求解
查看完整题目与答案
【单选题】背包问题的贪心算法所需的计算时间为()
A.
O(n2n)
B.
O(nlogn)
C.
O(2n)
D.
O(n)
查看完整题目与答案
【单选题】()不能保证求得0-1背包问题的最优解。
A.
分支限界法
B.
贪心算法
C.
回溯法
D.
动态规划策略
查看完整题目与答案
【简答题】0-1背包问题的回溯算法所需的计算时间为(),用动态规划算法所需的计算时间为()。
查看完整题目与答案
【多选题】0-1背包问题可用多种方法来求解:
A.
动态规划法
B.
贪心法
C.
回溯法
D.
分支限界法
查看完整题目与答案
【单选题】背包问题是以下哪种优化模型?
A.
有约束非线性规划
B.
0-1规划
C.
无约束非线性规划
D.
线性规划
查看完整题目与答案
【单选题】背包问题的贪心算法所需的计算时间为( )。
A.
O(n 2 )
B.
O(nlogn)
C.
O(2)
D.
O(n)
查看完整题目与答案
【简答题】用分支限界法解0/1背包问题,若物品i选入,则x[i]=1,否则x[i]=0。如何选用上下界函数?
查看完整题目与答案
【判断题】背包问题的决策变量与状态变量均为连续变量;
A.
正确
B.
错误
查看完整题目与答案