下图是0-1背包问题实例n=3,C=25,w[]={10,15,20},v[]={20,30,25}的解空间树,用回溯法搜索解空间树,因为不满足约束函数被剪枝的节点有()
A: ③⑦
B: ③⑤
C: ④⑤
D: ④⑦
A: ③⑦
B: ③⑤
C: ④⑤
D: ④⑦
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叉树或者排列树来说，回溯法搜索时对每个分支的剪枝条件（函数）是完全相同的。
内容
- 0
回溯法搜索解空间树时,常用的两种剪枝函数是()? A: 约束函数 B: 限界函数 C: 目标函数
- 1
用回溯法求解0-1背包问题时,该问题的解空间树为______ 。
- 2
回溯法搜索解空间树时,通常采用()函数来避免无效搜索,提高效率。 A: 约束函数 B: 预测函数 C: 限界函数 D: 剪枝函数
- 3
0-1背包问题用回溯法(利用约束函数和限界函数剪枝)求最优解,已知c=15,n=4,p[]:{16,9,20,6},w[]: {4,3,10,5} ,请问根结点的右孩子结点的上界是 ( ).(注:c是背包容量,p是价值数组,w是重量数组,左孩子表示装入物品,右孩子表示不装入物品 ) A: 31.4 B: 31 C: 25 D: 22
- 4
回溯法搜索解空间树时，常用的两种剪枝函数为 、 。