0-1背包问题 C语音代码

以下是一个简单的0-1背包问题的C语言代码实现：

#include<stdio.h>

// 定义背包容量和物品数量的最大值
#define MAX_C 100
#define MAX_N 100

// 定义物品的结构体
struct Item {
    int weight;     // 物品的重量
    int value;      // 物品的价值
};

// 定义背包问题的函数
int knapsack(int n, int c, struct Item items[]) {
    int dp[MAX_N+1][MAX_C+1];   // 定义动态规划数组
    int i, j;
    
    // 初始化第一行和第一列
    for(i=0; i<=n; i++) {
        dp[i][0] = 0;
    }
    for(j=0; j<=c; j++) {
        dp[0][j] = 0;
    }
    
    // 计算动态规划数组
    for(i=1; i<=n; i++) {
        for(j=1; j<=c; j++) {
            if(items[i-1].weight <= j) {
                dp[i][j] = (dp[i-1][j] > dp[i-1][j-items[i-1].weight] + items[i-1].value) ? dp[i-1][j] : dp[i-1][j-items[i-1].weight] + items[i-1].value;
            }
            else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    // 返回最优解
    return dp[n][c];
}

int main() {
    int n, c;       // 物品数量和背包容量
    struct Item items[MAX_N];    // 存储物品的数组
    int i;
    
    // 读入物品数量和背包容量
    scanf("%d%d", &n, &c);
    
    // 读入每个物品的重量和价值
    for(i=0; i<n; i++) {
        scanf("%d%d", &items[i].weight, &items[i].value);
    }
    
    // 输出最优解
    printf("%d\n", knapsack(n, c, items));
    
    return 0;
}

这个代码使用了动态规划算法来解决0-1背包问题。它使用一个二维数组来存储子问题的最优解，然后逐步计算出整个问题的最优解。这个算法的时间复杂度是$O(nC)$，其中$n$是物品数量，$C$是背包容量。