01背包问题回溯法代码python

01背包问题是一个经典的动态规划问题，其目的是在有限的背包容量下，尽可能地装入更有价值的物品。回溯法是一种常用的解决此问题的方法之一。

以下是01背包问题回溯法的Python代码实现：

def backtracking(capacity, weights, values, idx, max_value, cur_weight):
    if idx == len(weights):
        if cur_weight <= capacity:
            return max(max_value, sum(values))
        else:
            return max_value
    else:
        # 不选当前物品
        max_value = backtracking(capacity, weights, values, idx+1, max_value, cur_weight)
        # 选当前物品
        if cur_weight + weights[idx] <= capacity:
            max_value = backtracking(capacity, weights, values, idx+1, max_value, cur_weight+weights[idx])
        return max_value

其中，`capacity`为背包的容量，`weights`为物品重量列表，`values`为物品价值列表，`idx`为当前物品的下标，`max_value`为当前最大价值，`cur_weight`为当前已经放入背包中的物品总重量。