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

在Python中，回溯法是一种通过递归的方式来解决问题的算法，常用于解决一些组合优化问题，如01背包问题。下面是一个简单的01背包问题的回溯法解题代码示例：

def knapsack(W, wt, val, n):
    def backtrack(i, cur_weight, remaining_capacity):
        if i == n or remaining_capacity == 0:
            # 如果所有物品都已处理或者剩余容量为0，则计算当前价值
            if i == n:
                print("Items included:", [j for j in range(i) if taken[j]])
                print("Total weight:", cur_weight)
                print("Total value:", sum(val[j] * taken[j] for j in range(i)))
            return

        # 如果当前物品重量小于等于剩余容量，考虑放入和不放入的情况
        if wt[i] <= remaining_capacity:
            taken[i] = True
            backtrack(i + 1, cur_weight + wt[i], remaining_capacity - wt[i])
            taken[i] = False  # 回溯，尝试下一个物品

        else:
            # 如果当前物品重量大于剩余容量，直接跳过，因为放不下
            backtrack(i + 1, cur_weight, remaining_capacity)

    # 初始化全局变量
    taken = [False] * n
    backpack_val = 0
    backpack_weight = W

    # 调用回溯函数开始搜索
    backtrack(0, 0, backpack_weight)

# 示例参数：背包容量W=50，物品权重wt=[10, 20, 30], 物品价值val=[60, 100, 120], 物品数量n=3
knapsack(50, [10, 20, 30], [60, 100, 120], 3)

在这个代码里，`backtrack`函数通过递归枚举每个物品是否装入背包，然后计算剩余容量下背包可以达到的最大价值。如果当前物品能完全放入背包，就尝试放入并继续递归；否则直接忽略。