用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];

void solve() {
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) {
                dp[i][j] = dp[i + 1][j];
            } else {
                dp[i][j] = (dp[i + 1][j] > dp[i + 1][j - w[i]] + v[i]) ? dp[i + 1][j] : dp[i + 1][j - w[i]] + v[i];
            }
        }
    }
    printf("%d\n", dp[0][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;
}

其中，`MAX_N` 和 `MAX_W` 分别表示物品个数和背包容量的最大值。

首先输入物品个数 `N` 和背包容量 `W`，然后输入每个物品的重量 `w[i]` 和价值 `v[i]`。

`dp[i][j]` 表示从第 `i` 个物品开始选，容量为 `j` 的背包可以获得的最大价值。

接着，我们从后往前遍历每个物品，从小到大遍历背包容量，计算 `dp[i][j]` 的值。

如果当前物品的重量 `w[i]` 大于当前背包容量 `j`，则不能选这个物品，`dp[i][j]` 的值等于 `dp[i + 1][j]`。

否则，我们可以选择放入当前物品或不放入，选取价值高的方案，即 `dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])`。

最后得到的 `dp[0][W]` 就是我们要求的最大价值。

该算法的时间复杂度为 $O(NW)$，可以通过在线测试网站进行测试和优化。