01背包问题蛮力法c语言代码

01背包问题是一个经典的动态规划问题，通常用于资源分配决策。在C语言中，蛮力法（Brute Force）即穷举所有可能的情况来求解。下面是一个简单的C语言代码示例，假设我们有一个物品数组`items[]`，每个物品有自己的价值`value[i]`和重量`weight[i]`，背包容量为`W`：

#include <stdio.h>

#define MAX_ITEMS 50 // 最大物品数
#define MAX_W 100   // 背包最大容量

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

void knapsack(int W, Item items[], int n) {
    int dp[MAX_W + 1]; // 动态规划数组，dp[i]表示前i个物品能装入的最大价值

    // 初始化数组，第一个位置不可能放物品，价值为0
    for (int i = 0; i <= W; i++) {
        dp[i] = 0;
    }

    // 穷举每个物品，考虑是否放入背包
    for (int i = 1; i <= n; i++) {
        for (int w = items[i - 1].weight; w <= W; w++) {
            // 如果物品可以完全放入背包，选择价值更大的方案
            if (items[i - 1].weight <= w) {
                dp[w] = max(dp[w], dp[w - items[i - 1].weight] + items[i - 1].value);
            } else {
                // 如果物品无法完全放入，只考虑部分放入
                dp[w] = dp[w];
            }
        }
    }

    printf("背包内最大价值: %d\n", dp[W]);
}

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

    knapsack(W, items, n);

    return 0;
}