采用动态规划求解0/1背包问题用C语言实现

下面是一个采用动态规划求解0/1背包问题的C语言实现：

#include <stdio.h>
#include <stdlib.h>

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

int N;          // 物品数量
int W;          // 背包容量
int w[MAX_N];   // 各个物品的重量
int v[MAX_N];   // 各个物品的价值
int dp[MAX_N+1][MAX_W+1];    // 动态规划数组

// 求解0/1背包问题
int solve() {
    int i, j;
    for (i = 0; i <= N; i++) {
        for (j = 0; j <= W; j++) {
            if (i == 0 || j == 0) {
                // 边界条件，当物品数量为0或背包容量为0时，价值为0
                dp[i][j] = 0;
            } else if (j < w[i-1]) {
                // 当前物品放不下时，价值与前一个相同
                dp[i][j] = dp[i-1][j];
            } else {
                // 当前物品可放下时，取放和不放中价值最大的一个
                dp[i][j] = (dp[i-1][j-w[i-1]]+v[i-1] > dp[i-1][j]) ? dp[i-1][j-w[i-1]]+v[i-1] : dp[i-1][j];
            }
        }
    }
    return dp[N][W];
}

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

该实现中，动态规划数组 `dp[N+1][W+1]` 表示在前 N 个物品、背包容量为 W 的情况下，可获得的最大价值。通过两层循环，遍历所有情况，并填充动态规划数组，最后返回 `dp[N][W]` 即可得到最大价值。具体实现可参考注释。