01背包问题动态规划C++代码

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

#include <stdio.h>
#define MAX_N 1000
#define MAX_W 1000

int max(int a, int b) {
    return a > b ? a : b;
}

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N + 1][MAX_W + 1];

int main() {
    scanf("%d%d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
            }
        }
    }

    printf("%d\n", dp[n][W]);
    return 0;
}

这段代码使用了一个二维数组 `dp`，其中 `dp[i][j]` 表示前 `i` 个物品中，容量为 `j` 的背包所能装下的最大价值。状态转移方程为：

dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i])

其中 `w[i]` 和 `v[i]` 分别表示第 `i` 个物品的重量和价值。如果背包容量 `j` 小于当前物品重量 `w[i]`，则不能装入，直接继承上一个物品的最大价值即可。否则，可以选择不装入当前物品，即继承上一个物品的最大价值，或者装入当前物品，此时背包容量减少 `w[i]`，价值增加 `v[i]`。最终的答案为 `dp[n][W]`，即前 `n` 个物品中容量为 `W` 的背包所能装下的最大价值。