简单背包问题c语言枚举

简单背包问题（0-1 Knapsack Problem）是一个经典的计算机科学问题，目标是在给定一组物品（每个物品有自己的价值和重量）中，选择总重量不超过背包容量的最大价值组合。在C语言中，我们可以使用枚举法来解决这个问题。下面是一种基本的思路：

1. 定义一个枚举结构体，用于表示每种物品，包含物品的价值`value`和重量`weight`。

typedef enum {
    Item1,
    Item2,
    // 其他物品...
} Item;

2. 使用二维数组记录子问题的解，`dp[i][j]`表示前i个物品中选择总重量不超过j的背包最大价值。
3. 遍历所有物品和背包容量，对于每一个物品，有两种选择：放入背包或不放入。通过比较当前物品的价值加上之前状态（不放物品的情况）和只放当前物品的情况，选择最优值并更新`dp`数组。

for (int i = 1; i <= n; ++i) { // n为物品数量
    for (int j = 0; j <= W; ++j) { // W为背包容量
        if (weights[i - 1] <= j) {
            dp[i][j] = max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weights[i - 1]]);
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}

4. 最终，`dp[n][W]`就是背包能装下的最大价值。