枚举法解决0/1背包问题c代码

枚举法是一种通过遍历所有可能性来求解0/1背包问题的动态规划方法。对于每个物品i，我们可以选择将它放入背包，此时价值为item[i]，重量为weight[i]；也可以选择不放。下面是使用C语言的一个简单示例：

#include <stdio.h>

// 定义背包容量和物品数组
#define CAPACITY 50
#define NUM_ITEMS 4
int capacity = CAPACITY;
int weight[NUM_ITEMS] = {10, 20, 30, 40};
int value[NUM_ITEMS] = {60, 100, 120, 150};

// 动态规划函数，返回最大价值
int knapsack(int W) {
    int dp[NUM_ITEMS + 1][W + 1]; // 初始化二维数组

    // 枚举每个物品
    for (int i = 0; i <= NUM_ITEMS; i++) {
        // 如果背包容量为0，不能装入物品
        if (W == 0)
            dp[i][W] = 0;
        else {
            // 如果物品能装下，选择是否装入，取两者最大值
            dp[i][W] = max(dp[i - 1][W], dp[i - 1][W - weight[i]] + value[i]);
        }
    }

    return dp[NUM_ITEMS][W];
}

int main() {
    int max_value = knapsack(capacity);
    printf("最大价值为：%d\n", max_value);

    return 0;
}

在这个例子中，`knapsack`函数通过递推计算dp数组，记录到当前背包容量为止可以得到的最大价值。函数`max`是一个辅助函数，用于比较两个数的最大值。