下图是0-1背包问题实例n=3,C=25,w[]={10,15,20},v[]={20,30,25}的解空间树,用回溯法搜索解空间树,因为不满足约束函数被剪枝的节点有()
A: ③⑦
B: ③⑤
C: ④⑤
D: ④⑦
A: ③⑦
B: ③⑤
C: ④⑤
D: ④⑦
举一反三
- 使用回溯法求解0-1背包问题： 有3个物品，其重量分别是{16, 15, 15}，价值分别为{45, 25, 25}，背包的容量为30。 （1）描述回溯法的基本思想。 （2）说明你在搜索过程中所使用的约束函数和限界函数。 （3）画出解空间树（即状态空间树），写出各步搜索时解空间树的变化情况
- 请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20，15，10}，价值为{20，30，25}，背包容量为25时搜索空间树。
- 回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和
- 回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和______ 。
- 回溯法中，下面关于显约束、隐约束及剪枝条件等的解释不正确的是？ A: 显约束决定了一个扩展结点可展开的分支个数及每个分支的取值 B: 隐约束是解空间树的剪枝条件，是在搜索时剪掉不满足隐约束的分支，避免无效搜索 C: 隐约束包含约束函数和限界函数。对于子集树，约束函数对0分支剪枝，限界函数对1分支剪枝。 D: 对解空间树是n叉树或者排列树来说，回溯法搜索时对每个分支的剪枝条件（函数）是完全相同的。