递归回溯法求解0/1背包问题python完整代码

下面是使用递归回溯法求解0/1背包问题的Python完整代码：

def knapsack(i, j):
    if i == 0 or j == 0:
        return 0
    if w[i-1] > j:
        return knapsack(i-1, j)
    else:
        return max(knapsack(i-1, j), p[i-1] + knapsack(i-1, j-w[i-1]))

n = 5  # 物品数量
W = 10  # 背包容量
w = [2, 5, 4, 2, 3]  # 物品重量列表
p = [6, 3, 5, 4, 6]  # 物品价值列表

max_profit = knapsack(n, W)

print("最大总价值为：", max_profit)

其中，`knapsack`函数是递归回溯函数，`i`表示当前选到第几个物品，`j`表示当前背包容量。当`i`或`j`等于0时，返回0。如果第`i`个物品的重量大于当前背包容量`j`，则不能选第`i`个物品，继续考虑选前`i-1`个物品的最优解，即递归调用`knapsack(i-1, j)`。否则，考虑选或不选第`i`个物品，取两者之间的最大值，即`max(knapsack(i-1, j), p[i-1] + knapsack(i-1, j-w[i-1]))`。在程序最后，输出最大总价值。