python回溯法实现01背包问题

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

def knapsack_backtracking(values, weights, capacity):
    n = len(values)
    best_value = -1
    current_value = 0
    current_weight = 0
    # 定义回溯函数
    def backtrack(i):
        nonlocal best_value, current_value, current_weight
        if i == n:  # 搜索完所有物品
            if current_value > best_value:
                best_value = current_value
            return
        if current_weight + weights[i] <= capacity:  # 尝试选择第i个物品
            current_weight += weights[i]
            current_value += values[i]
            backtrack(i+1)
            current_weight -= weights[i]
            current_value -= values[i]
        backtrack(i+1)  # 尝试不选择第i个物品
    backtrack(0)
    return best_value

其中，`values` 和 `weights` 分别表示物品的价值和重量，`capacity` 表示背包的容量。函数 `backtrack(i)` 表示对于第 `i` 个物品，我们做出选择（放进背包）或不选择（不放进背包）两个决策。当 `i` 等于 `n` 时，即搜索完了所有物品，我们需要判断当前价值是否是最大的。最终，函数返回最大的价值。

使用方法如下：

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
best_value = knapsack_backtracking(values, weights, capacity)
print(best_value)  # 输出 220

在这个例子中，我们有3个物品，它们的价值分别是60、100和120，重量分别是10、20和30。我们的背包容量是50。最终，我们可以选择第1个和第3个物品，得到的最大价值是220。