使用动态规划方法求解0-1背包问题 c语言代码

以下是基于动态规划方法求解0-1背包问题的 C 语言代码：

#include <stdio.h>

#define MAX_N 100
#define MAX_C 1000

int n, C;
int w[MAX_N], v[MAX_N];
int f[MAX_N][MAX_C];

void dp() {
    int i, j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= C; j++) {
            if (j < w[i])
                f[i][j] = f[i - 1][j];
            else
                f[i][j] = f[i - 1][j] > f[i - 1][j - w[i]] + v[i] ? f[i - 1][j] : f[i - 1][j - w[i]] + v[i];
        }
    }
}

int main() {
    printf("请输入物品个数n和背包容量C：\n");
    scanf("%d%d", &n, &C);
    printf("请输入每个物品的重量和价值：\n");
    int i;
    for (i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    dp();
    printf("最大价值为：%d", f[n][C]);
    return 0;
}

首先定义了 MAX_N 和 MAX_C 两个常量，分别表示物品个数和背包容量的最大值。然后定义了 n、C、w 和 v 四个数组，分别表示物品个数、背包容量、每个物品的重量和价值。最后定义了 f 数组来保存状态转移的结果。

在 dp 函数中，使用两个循环遍历所有的状态，并根据状态转移方程来更新 f 数组的值。

最后在 main 函数中，输入物品个数、背包容量、每个物品的重量和价值，调用 dp 函数求解，并输出最大价值。