利用C语言解决0-1背包问题完整代码

0-1背包问题是一种经典的动态规划问题，在C语言中可以通过递归和记忆化搜索（也称为动态规划表）来求解。这里是一个简单的解决方案：

#include <stdio.h>

// 定义物品的结构体
typedef struct {
    int weight;   // 物品重量
    int value;    // 物品价值
} Item;

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

    // 遍历所有物品
    for (int i = 0; i <= n; i++) { 
        // 如果没有物品，直接返回0
        if (i == 0 || W == 0)
            dp[i][W] = 0;
        else {
            // 如果当前物品能装入背包，比较包含该物品和不包含的选择
            dp[i][W] = max(items[i - 1].value, dp[i - 1].value);
        }
    }

    return dp[n][W];  // 返回背包最大价值
}

int main() {
    int W = 50;  // 背包容量
    Item items[] = { {10, 60}, {20, 100}, {30, 120} };  // 物品数组
    int n = sizeof(items) / sizeof(items[0]);  // 物品数量

    printf("背包的最大价值是: %d\n", knapsack(W, items, n));

    return 0;
}

在这个代码中，`knapsack` 函数通过计算每个状态（物品i和剩余容量W）下的最优值来解决问题。`max` 函数用于选择两个选项中的较大值。