python使用动态规划法求解0-1背包问题

以下是使用动态规划法求解0-1背包问题的Python代码：

def knapsack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    return K[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapsack(W, wt, val, n)) # 输出：220

解释：

首先，我们定义一个二维数组K，其中K[i][w]表示在前i个物品中，容量为w的背包所能装下的最大价值。

然后，我们使用两个循环来填充这个数组。外层循环遍历物品，内层循环遍历容量。对于每个物品i和容量w，我们有两种选择：将物品i放入背包或不放入背包。如果将物品i放入背包，那么背包的容量就会减少wt[i-1]，价值就会增加val[i-1]。如果不放入背包，那么背包的容量和价值都不会变化。我们选择这两种选择中的最优解，即max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])，填入K[i][w]中。

最后，我们返回K[n][W]，即前n个物品中，容量为W的背包所能装下的最大价值。