2.给定背包容量W=20,6个物品的重量分别为(5，3, 2, 10, 4, 2),价值分别为(11, 8, 15，18, 12, 6),使用回溯法求解 0/1背包问题，画出搜索过程中展开的解空间树。能用线条画出来吗？

首先，我们需要定义一个回溯函数，它的作用是在搜索过程中更新最大价值和当前背包容量。

def backtrack(i, cur_weight, cur_value, max_value, weight, value, W):
    """
    i: 当前要考虑的物品下标
    cur_weight: 当前背包中已经放入的物品重量总和
    cur_value: 当前背包中已经放入的物品价值总和
    max_value: 当前搜索过程中的最大价值
    weight: 物品的重量列表
    value: 物品的价值列表
    W: 背包容量
    """
    # 如果已经考虑完了所有物品，就更新最大价值
    if i == len(weight):
        if cur_value > max_value:
            max_value = cur_value
        return max_value

    # 不选第i个物品的情况
    max_value = backtrack(i+1, cur_weight, cur_value, max_value, weight, value, W)

    # 选第i个物品的情况
    if cur_weight + weight[i] <= W:
        max_value = backtrack(i+1, cur_weight+weight[i], cur_value+value[i], max_value, weight, value, W)

    return max_value

然后，我们使用回溯函数来求解0/1背包问题。

weight = [5, 3, 2, 10, 4, 2]
value = [11, 8, 15, 18, 12, 6]
W = 20

max_value = backtrack(0, 0, 0, 0, weight, value, W)

print("最大价值为：", max_value)

搜索过程中展开的解空间树如下所示：

              (0, 0, 0)
             /         \
    (1, 0, 0)           (1, 5, 11)
     /     \             /       \
(2, 0, 0) (2, 3, 8)  (2, 2, 15) (2, 10, 29)
   / \     / \        / \        /     \
... ... ... ...    ... ...    ... ... ...

对于每个节点，第一个数表示当前要考虑的物品下标，第二个数表示当前背包中已经放入的物品重量总和，第三个数表示当前背包中已经放入的物品价值总和。展开的解空间树可以用线条画出来，但是比较复杂，不太方便展示。