用c++写一段01背包问题

以下是使用 C 语言编写的 01 背包问题示例代码：

#include <stdio.h>

#define MAX_N 100 // 物品数量最大值
#define MAX_W 1000 // 背包容量最大值

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

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

void solve()
{
    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]);
}

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

上面的代码使用了动态规划的思想，利用一个二维数组 `dp` 来记录各种状态下的最大价值。其中 `dp[i][j]` 表示前 i 个物品，背包容量为 j 时的最大价值。状态转移方程如下：

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

其中，如果当前物品的重量大于背包容量，那么直接继承前一个状态的最大价值，否则需要比较是否加入当前物品能够获得更大的价值。最终答案即为 `dp[n][W]`。