c语言0-1背包问题

0-1背包问题是一个经典的动态规划问题，可以用C语言进行求解。

问题描述：给定一个背包，容量为C；有n个物品，每个物品有自己的重量w[i]和价值v[i]。要求在不超过背包容量的情况下，选择一些物品放入背包，使得背包中物品的总价值最大。

解决方法：使用动态规划算法，定义一个二维数组dp[i][j]表示前i个物品中，容量为j的背包能够获得的最大价值。则对于第i个物品，有两种选择：放入背包或不放入背包，因此状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]), 其中w[i]是第i个物品的重量，v[i]是第i个物品的价值。

最终的解为dp[n][C]，即前n个物品中，容量为C的背包能够获得的最大价值。

以下是C语言代码实现：

#include <stdio.h>
#include <string.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int knapsack(int n, int C, int w[], int v[]) {
    int dp[n+1][C+1];
    memset(dp, 0, sizeof(dp)); // 初始化dp数组为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]);
            }
        }
    }
    return dp[n][C];
}

int main() {
    int n = 5;
    int C = 10;
    int w[] = {0, 2, 2, 6, 5, 4}; // 物品重量
    int v[] = {0, 6, 3, 5, 4, 6}; // 物品价值
    int ans = knapsack(n, C, w, v);
    printf("最大价值为：%d\n", ans);
    return 0;
}

以上代码中，我们使用了max宏定义来求两个数的最大值。在knapsack函数中，我们定义了一个二维数组dp来存储状态转移方程的结果。接着，使用两个嵌套的for循环，依次计算dp[i][j]的值。最终，返回dp[n][C]即为所求的最大价值。