回溯法求解0-1背包问题python代码

以下是使用回溯法求解0-1背包问题的Python代码：

def knapsack(bag_weight, weights, values, n):
    max_value = 0  # 最大价值
    cur_weight = 0  # 当前重量
    cur_value = 0  # 当前价值

    def backtrack(i):
        nonlocal max_value, cur_weight, cur_value

        if i == n:
            if cur_value > max_value:
                max_value = cur_value
            return

        if cur_weight + weights[i] <= bag_weight:
            cur_weight += weights[i]
            cur_value += values[i]
            backtrack(i + 1)
            cur_weight -= weights[i]
            cur_value -= values[i]

        backtrack(i + 1)

    backtrack(0)
    return max_value

其中，`bag_weight`表示背包的最大承重，`weights`表示每个物品的重量，`values`表示每个物品的价值，`n`表示物品数量。函数内部定义了一个嵌套函数`backtrack(i)`，表示从第`i`个物品开始考虑。对于每个物品，可以选择将其装入背包或不装入背包，如果装入背包，则更新当前重量和当前价值，并继续考虑下一个物品；如果不装入背包，则直接考虑下一个物品。当考虑完所有物品后，更新最大价值并返回。