c语言实现动态规划法求解0-1背包三个循

在C语言中，动态规划是一种常用的算法思想，常用于解决最优化问题，如0-1背包问题。0-1背包问题是一个经典的组合优化问题，给定一组物品，每种物品都有一个重量和一个价值，目标是在不超过背包容量的前提下，选择总价值最大的物品组合。

以下是使用动态规划（Bottom-Up approach）解决0-1背包问题的一个基础版实现：

#include <stdio.h>

int knapSack(int W, int wt[], int val[], int n) {
    int i, w;
    int dp[n+1][W+1]; // 创建一个二维数组存储动态规划结果

    // 初始化dp表的第一行和第一列
    for (i = 0; i <= n; i++)
        dp[i][0] = 0;

    // 对于每个物品，从0到当前物品
    for (i = 1; i <= n; i++) {
        // 对于每个背包容量，从0到当前物品的重量
        for (w = 1; w <= W; w++) {
            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函数
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;
}