01背包问题动态规划用C语言

01背包问题是一个经典的动态规划问题，它描述了在给定的一组物品中选择一些放入一个容量有限的背包，使得这些物品的总价值最大。在C语言中，我们可以用二维数组来表示状态，其中`dp[i][j]`表示前i个物品中能够装入重量不超过j的最大价值。

以下是基本的动态规划解决方案：

#include <stdio.h>

int knapSack(int W, int wt[], int val[], int n) {
    // 初始化一个二维数组，行代表物品，列代表剩余容量
    int dp[n + 1][W + 1];

    // 每种物品都有两个选择，要么不选（价值为0），要么选（取当前价值）
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (wt[i - 1] <= w)
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            else
                dp[i][w] = dp[i - 1][w];
        }
    }

    return dp[n][W];
}

// 使用max函数替换实际环境中的max，因为C标准库没有这个函数
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int W = 50; // 背包容量
    int wt[] = {10, 20, 30}; // 物品重量
    int val[] = {60, 100, 120}; // 物品价值
    int n = sizeof(wt) / sizeof(wt[0]);

    printf("最大价值: %d\n", knapSack(W, wt, val, n));

    return 0;
}