C语言01背包问题代码和设计思路

以下是C语言的01背包问题代码和设计思路：

设计思路：
1. 定义一个二维数组dp[i][j]，表示前i个物品放入容量为j的背包中所能获得的最大价值。
2. 初始化dp数组，当i=0或j=0时，dp[i][j]均为0。
3. 对于每个物品i，分两种情况考虑：
a. 如果第i个物品的重量大于背包容量j，则不装入背包，此时dp[i][j] = dp[i-1][j]。
b. 如果第i个物品的重量小于等于背包容量j，则可以选择装入或不装入背包，取两者中的最大值，即dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。
4. 最终dp[n][C]即为所求的最大价值。

代码实现：

#include <stdio.h>
#define N 100
#define C 1000

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

int main() {
    int n, w[N], v[N], dp[N][C];
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= C; j++) {
        dp[0][j] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            if (j < w[i]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }
    printf("%d\n", dp[n][C]);
    return 0;
}