枚举法求解01背包问题

枚举法求解01背包问题通常用于寻找给定物品集合中能够使得背包重量不超过限制的最大价值组合。这个算法的基本思路是遍历所有可能的物品选择，对于每个物品，如果放入背包，就更新当前状态下背包所能容纳的价值；如果不放，保持原有的价值不变。这是贪心算法的一种应用。

以下是使用枚举法（暴力搜索）的一个简单示例，用C语言编写：

#include <stdio.h>

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

// 求解01背包问题
int knapsack(int W, Item items[], int n) {
    int i, w;
    for (i = 0; i <= n; i++) { // 对于每种可能的数量（包括不选）
        for (w = 0; w <= W; w++) { // 对于每个可能的总重量
            if (i == 0 || w == 0) // 如果没有物品或背包为空，价值为0
                result[W][i] = 0;
            else if (items[i - 1].weight <= w) // 如果物品能完全装入背包
                result[W][i] = max(result[W][i - 1], result[W - items[i - 1].weight][i - 1] + items[i - 1].value);
            else // 如果物品不能装入，直接取不装的情况
                result[W][i] = result[W][i - 1];
        }
    }
    return result[W][n]; // 返回最大价值
}

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;
}

在这个例子中，`result` 是一个二维数组，用来存储以当前状态下的背包容量和剩余物品数为目标值时的最大价值。`max` 函数用来返回两个数中的较大值。