c语言求解背包问题的算法设计代码

在C语言中，解决0-1背包问题通常会使用动态规划(Dynamic Programming)方法，特别是贪心法或称为背包算法的一种变种——“最值回溯”。这里提供一个简单的代码示例，用于解决给定一组物品（每个物品有自己的价值`value[i]`和重量`weight[i]`），以及背包最大容量`W`的情况下，如何选择物品使得总价值最大。

#include <stdio.h>

// 定义物品结构体
typedef struct {
    int value;
    int weight;
} Item;

// 动态规划函数
int knapsack(int W, Item items[], int n) {
    // 初始化二维数组 dp
    int dp[n+1][W+1];

    // 填充dp表
    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 (items[i-1].weight <= w)
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i-1].weight] + items[i-1].value);
            else
                dp[i][w] = dp[i-1][w];
        }
    }

    return dp[n][W]; // 返回最终的最大价值
}

// 主函数测试
int main() {
    Item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = sizeof(items) / sizeof(items[0]);
    int W = 50;
    int result = knapsack(W, items, n);
    printf("最大价值: %d\n", result);
    return 0;
}