c语言实现完全背包问题

在C语言中，完全背包问题是一个经典的动态规划问题，通常用于求解在给定总重量限制下，如何选择物品以达到最大的价值。以下是使用动态规划解决该问题的一个基本算法：

#include <stdio.h>

// 定义背包问题函数
int knapSack(int W, int wt[], int val[], int n) {
    // 初始化一个二维数组，dp[i][w]表示前i个物品在总重量w下的最大价值
    int dp[n+1][W+1];

    // 构建动态规划表
    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];  // 返回总重量为W时的最大价值
}

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

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

    return 0;
}

在这个例子中，`knapSack`函数接受背包容量、物品重量数组、物品价值数组和物品数量作为输入。它通过遍历所有可能的组合，计算并存储每个状态下的最大价值，最后返回总重量限制下的最大价值。