用C语言战实现背包问题

以下是一个基于动态规划的背包问题的C语言实现：

#include <stdio.h>

#define MAX_N 100
#define MAX_W 1000

int n; // 物品个数
int w[MAX_N]; // 物品重量
int v[MAX_N]; // 物品价值
int dp[MAX_N+1][MAX_W+1]; // 动态规划表格

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

int main() {
    scanf("%d", &n);
    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 <= MAX_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][MAX_W]);

    return 0;
}

在这个实现中，我们使用一个二维数组 `dp` 来记录动态规划的过程。其中 `dp[i][j]` 表示前 `i` 个物品在背包容量为 `j` 的情况下的最大价值。我们从 `dp[0][0]` 开始，逐步填充表格，直到 `dp[n][MAX_W]`，最终的结果就是在背包容量不超过 `MAX_W` 的情况下，前 `n` 个物品的最大价值。

该实现的时间复杂度为 $O(nW)$，其中 $W$ 是背包的最大容量。