01背包问题回溯法

01背包问题是指有一个背包，它的容量为C（capacity），现在有n种不同的物品，每种物品的重量为w[i]，价值为v[i]。要求在这些物品中选择一些放入背包中，使得背包中物品的总重量不超过C，且价值最大。这就是著名的01背包问题。

回溯法是一种通过尝试所有可能的情况来解决问题的算法。我们可以使用回溯法来解决01背包问题。具体步骤如下：

1. 定义一个全局变量max_val，用于记录当前的最大价值。
2. 定义一个回溯函数backtrack(i, curr_w, curr_v)，其中i表示当前考虑的物品编号，curr_w表示当前已经放入背包的物品总重量，curr_v表示当前已经放入背包的物品总价值。
3. 每次调用回溯函数时，首先判断是否已经考虑完了所有物品，如果是，则更新max_val。
4. 如果当前物品的重量加上已经放入背包的物品总重量小于等于C，则可以将该物品放入背包中，递归调用回溯函数backtrack(i+1, curr_w+w[i], curr_v+v[i])。
5. 如果不放该物品，则直接递归调用回溯函数backtrack(i+1, curr_w, curr_v)。
6. 回溯函数返回时，将已经放入背包的物品取出，继续考虑下一个物品。

代码如下：

max_val = 0

def backtrack(i, curr_w, curr_v, w, v, C):
    global max_val
    if i == len(w):
        max_val = max(max_val, curr_v)
        return
    if curr_w + w[i] <= C:
        backtrack(i+1, curr_w+w[i], curr_v+v[i], w, v, C)
    backtrack(i+1, curr_w, curr_v, w, v, C)

w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
C = 8
backtrack(0, 0, 0, w, v, C)
print(max_val)  # 输出最大价值为 11

在上面的代码中，我们定义了w和v数组来存储每个物品的重量和价值，C为背包的容量。我们首先将max_val初始化为0，然后调用回溯函数backtrack(0, 0, 0, w, v, C)来开始回溯。最后输出max_val即为最大价值。