0/1背包代码C语言

在C语言中，0/1背包问题通常使用动态规划方法来解决。这是一个经典的优化问题，假设你有一个背包，可以装物品，每个物品有一个重量和一个价值。你可以选择是否放入该物品，但每个物品只能取一次。目标是找到一个组合，使得背包的总重量不超过限制，同时总价值最大。

以下是简单的0/1背包算法的C语言实现：

#include <stdio.h>

// 定义背包的最大容量和物品数组
#define CAPACITY 10
#define NUM_ITEMS 5

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

// 动态规划函数
int knapsack(int capacity, Item items[]) {
    int dp[CAPACITY + 1]; // dp[i]表示容量为i时的最大价值
    for (int i = 1; i <= capacity; i++) {
        dp[i] = 0;
        for (int j = 0; j < NUM_ITEMS && items[j].weight <= i; j++) {
            // 如果物品能完全装入背包，选择它和不选之间取最大值
            dp[i] = max(dp[i], dp[i - items[j].weight] + items[j].value);
        }
    }
    return dp[capacity];
}

// 比较函数（这里用整形作为比较）
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    Item items[NUM_ITEMS] = { {10, 60}, {20, 100}, {30, 120}, {40, 150}, {50, 180} }; // 示例物品列表
    int capacity = 50; // 背包容量

    printf("Max value with %d capacity: %d\n", capacity, knapsack(capacity, items));
    return 0;
}

这个程序首先初始化一个dp数组，然后通过两层循环遍历所有可能性，每次判断当前物品是否能放入背包，并更新dp值。最后返回背包满容量时的最大价值。