用回溯法解决0-1背包问题时，对于左子树【装入物品】而言，剪枝条件是( )。
A: 得到一个可行解
B: 得到一个最优解
C: 当前物品不能装入背包
D: 当前物品能装入背包
A: 得到一个可行解
B: 得到一个最优解
C: 当前物品不能装入背包
D: 当前物品能装入背包
举一反三
- 用回溯法解决0-1背包问题时，对于左子树【装入物品】而言，剪枝条件是( )。
- 如果从最后一个物品开始装入背包，0-1背包问题的最优解为( )。【n为物品数量，c为背包容量】
- 0-1背包问题与部分背包问题的区别在于（ ）。 A: 若用贪心算法解决部分背包问题，只能得到近似最优解 B: 在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分 C: 若用贪心算法解决0-1背包问题，只能得到近似最优解 D: 没有区别，它们的含义相同
- 【多选题】0-1背包问题与部分背包问题的区别在于()。 A. 若用贪心算法解决0-1背包问题，只能得到近似最优解 B. 若用贪心算法解决部分背包问题，只能得到近似最优解 C. 在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分 D. 没有区别，它们的含义相同
- 0-1背包问题的回溯算法，下面的解释不正确的是 A: 解空间树是子集树 B: 左(1)分支的剪枝：当选择装入背包的物品重量之和超过背包容量时就剪枝。 C: 右（0）分支的剪枝：已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值（物品可分割，即用背包问题的贪心算法求得的最大价值）>当前最优值bestp, 就剪枝. D: 当搜索至叶子结点时，一定是发现了到目前为止最好的解