使用回溯法求解0-1背包问题： 有3个物品，其重量分别是{16, 15, 15}，价值分别为{45, 25, 25}，背包的容量为30。 （1）描述回溯法的基本思想。 （2）说明你在搜索过程中所使用的约束函数和限界函数。 （3）画出解空间树（即状态空间树），写出各步搜索时解空间树的变化情况
举一反三
- 请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20，15，10}，价值为{20，30，25}，背包容量为25时搜索空间树。
- 用回溯法求解0-1背包问题时,该问题的解空间树为______ 。
- 下图是0-1背包问题实例n=3,C=25,w[]={10,15,20},v[]={20,30,25}的解空间树,用回溯法搜索解空间树,因为不满足约束函数被剪枝的节点有() A: ③⑦ B: ③⑤ C: ④⑤ D: ④⑦
- 分支限界法解0-1背包问题时的解空间树是______ 。
- 对n个物品的0-1背包问题用回溯法求解，其解空间树有个多少个叶子结点（ ） A: n2 B: nlogn C: n！ D: 2n