采用回溯法编程实现0-1背包问题Python

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

def knapsack(weights, values, capacity):
    """
    :param weights: 物品重量列表
    :param values: 物品价值列表
    :param capacity: 背包容量
    :return: 最大价值和
    """
    def backtrack(i, cw, cv):
        nonlocal max_value
        if i == n or cw == capacity:
            max_value = max(max_value, cv)
            return

        # 选择不装第i个物品
        backtrack(i + 1, cw, cv)

        # 选择装第i个物品
        if cw + weights[i] <= capacity:
            backtrack(i + 1, cw + weights[i], cv + values[i])

    n = len(weights)
    max_value = 0
    backtrack(0, 0, 0)
    return max_value

使用示例：

weights = [2, 2, 4, 6, 3]
values = [3, 4, 8, 9, 6]
capacity = 9

max_value = knapsack(weights, values, capacity)
print(max_value)  # 输出 18

上述代码中，`backtrack` 函数是回溯函数，它的三个参数分别是：当前考虑到的物品下标 `i`，当前背包的重量 `cw` 和当前背包的价值 `cv`。在回溯函数中，我们首先选择不装第 `i` 个物品，然后选择装第 `i` 个物品（当且仅当当前背包容量可以容纳第 `i` 个物品时才选择装）。在回溯过程中，我们不断更新最大价值和 `max_value`。回溯结束后，`max_value` 即为最大价值和。

在本题中，由于每个物品只有装或者不装两种选择，因此回溯树的每个节点的度数都为2，回溯树的深度为物品的个数 `n`。因此，回溯法的时间复杂度为 $O(2^n)$，不过实际上由于我们使用了剪枝（即当当前背包容量达到背包容量上限时不再继续搜索），因此实际运行的时间要小于 $O(2^n)$。