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