动态规划法求解背包问题用c语言完整代码

动态规划是一种解决问题的有效方法，特别适用于背包问题这类优化问题。以下是使用C语言实现的0-1背包问题的动态规划算法示例：

#include <stdio.h>
#include <limits.h>

int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int dp[W + 1]; // 存储子问题的最优解

    for (i = 0; i <= W; i++) {
        dp[i] = 0; // 初始化，表示空背包的价值
        for (w = 1; w <= n && i >= wt[w]; w++) {
            // 如果物品能装下，取最大价值
            dp[i] = max(dp[i], dp[i - wt[w]] + val[w]);
        }
    }

    return dp[W];
}

// 辅助函数，返回两个整数的最大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int W = 50, wt[] = {10, 20, 30}, val[] = {60, 100, 120};
    int n = sizeof(wt) / sizeof(wt[0]);

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

    return 0;
}

在这个代码中，`knapsack`函数通过二维数组dp计算出总重量为W时背包可以得到的最大价值。它遍历每个物品，并根据当前背包容量和剩余容量选择是否包含该物品。