给出代码和状态空间搜索树

好的，请看以下代码和状态空间搜索树。这里我使用Python实现回溯算法。

def backpack(idx, weight, value, chosen):
    global max_value
    # 如果背包已经装满了或者没有剩余的物品可供选择了，返回当前已经选中的物品的总价值
    if weight >= M or idx == len(weights):
        max_value = max(max_value, value)
        return

    # 选中当前物品
    chosen[idx] = 1
    backpack(idx+1, weight+weights[idx], value+values[idx], chosen)
    # 不选中当前物品
    chosen[idx] = 0
    backpack(idx+1, weight, value, chosen)

weights = [35, 30, 50, 60, 40, 10, 25]
values = [10, 40, 30, 50, 35, 40, 30]
M = 140
chosen = [0] * len(weights)
max_value = 0
backpack(0, 0, 0, chosen)
print(max_value)

状态空间搜索树的形状如下：

                 root
             /         \
           /             \
          选A             不选A
        /     \        /       \
   选B        不选B   选B       不选B
    / \        / \     / \       / \
选C 不选C  选C 不选C  选C 不选C  选C 不选C
...

其中，每个节点的表示方法为(idx, weight, value, chosen)，idx表示当前考虑的物品编号，weight表示当前已经选中的物品的总重量，value表示当前已经选中的物品的总价值，chosen表示当前已经选择的物品。在代码中，我们使用一个全局变量max_value来维护最大价值。每次更新max_value时，我们需要比较当前的价值value和max_value的大小，并将较大的值赋给max_value。