动态规划法解决0-1背包C语言

以下是用动态规划法解决0-1背包问题的C语言代码：

#include <stdio.h>
#define N 1000 // 物品个数的最大值
#define W 1000 // 背包容量的最大值

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

int main() {
    int n, m, w[N], v[N], dp[N][W]; // n表示物品个数，m表示背包容量，w表示物品重量，v表示物品价值，dp表示动态规划数组
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j >= w[i]) { // 如果背包容量足够放下第i件物品
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); // 取第i件物品和不取第i件物品中的最大值
            } else { // 如果背包容量不足以放下第i件物品
                dp[i][j] = dp[i - 1][j]; // 不放第i件物品
            }
        }
    }
    printf("%d\n", dp[n][m]); // 输出最大价值
    return 0;
}

这段代码使用二维数组`dp[i][j]`表示在前i个物品中，背包容量为j时的最大价值。通过递推填充`dp`数组，最终得到`dp[n][m]`即为问题的解。