动态规划解决01背包问题的伪代码

以下是01背包问题的动态规划伪代码：

function knapsack(weights, values, capacity):
    n = length(weights)
    dp = new array with size (n+1) * (capacity+1)
    for i from 0 to n:
        for j from 0 to capacity:
            if i == 0 or j == 0:
                dp[i][j] = 0
            else if weights[i-1] <= j:
                dp[i][j] = max(values[i-1] + dp[i-1][j-weights[i-1]], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][capacity]

其中，`weights`是物品的重量数组，`values`是物品的价值数组，`capacity`是背包的容量。`dp`是一个二维数组，用来记录不同物品放入不同容量背包的最大价值。在第i轮迭代中，我们考虑是否将第i个物品放入背包中，如果放入，则背包的容量减少`weights[i-1]`，价值增加`values[i-1]`，并且我们需要在容量为`j-weights[i-1]`时的最大价值基础上加上该物品的价值，因此状态转移方程为：`dp[i][j] = max(values[i-1] + dp[i-1][j-weights[i-1]], dp[i-1][j])`。如果不放入，则不会对最大价值产生影响，因此状态转移方程为：`dp[i][j] = dp[i-1][j]`。最终，`dp[n][capacity]`即为所求的最大价值。