回溯法解决01背包问题伪代码

以下是01背包问题的回溯法伪代码：

def backtrack_knapsack(capacity, weights, values, current_weight, current_value, index):
    if current_weight > capacity:
        return -1  # 超出了背包容量，返回无效解
    if index == len(weights):
        return current_value  # 已经考虑完所有物品，返回当前价值
    # 不选当前物品
    max_value = backtrack_knapsack(capacity, weights, values, current_weight, current_value, index+1)
    # 选当前物品
    new_weight = current_weight + weights[index]
    new_value = current_value + values[index]
    if new_weight <= capacity:
        max_value = max(max_value, backtrack_knapsack(capacity, weights, values, new_weight, new_value, index+1))
    return max_value

其中，`capacity`是背包容量，`weights`是物品重量的列表，`values`是物品价值的列表，`current_weight`和`current_value`是当前已经选中的物品重量和价值，`index`是当前考虑的物品下标。函数返回的是最大价值，如果返回-1表示无效解。