使用动态规划写一份01背包问题python代码实现

下面是使用动态规划实现01背包问题的Python代码：

def knapsack01(weights, values, capacity):
    n = len(weights)
    dp = [[0 for j in range(capacity+1)] for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, capacity+1):
            if weights[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][capacity]

其中，`weights`表示物品的重量列表，`values`表示物品的价值列表，`capacity`表示背包的容量。`n`表示物品的个数，`dp`是一个二维数组，其中`dp[i][j]`表示前i个物品放入容量为j的背包中所能获得的最大价值。

在代码中，我们使用两重循环，外层循环枚举物品，内层循环枚举背包容量。对于每一个物品，我们有两种选择：放入背包或不放入背包。如果选择放入背包，则当前背包的价值为`values[i-1]`，重量为`weights[i-1]`，我们需要从前面的物品中寻找剩余容量为`j-weights[i-1]`的最大价值，即`dp[i-1][j-weights[i-1]]`；如果选择不放入背包，则当前背包的价值为0，重量为0，我们需要从前面的物品中寻找剩余容量为`j`的最大价值，即`dp[i-1][j]`。我们取这两种选择中的较大值，作为当前背包的最大价值。

最后，我们返回`dp[n][capacity]`，即前n个物品放入容量为capacity的背包中所能获得的最大价值。