编辑代码

#include <stdio.h>

// 定义最大物品数量和背包容量
#define MAX_ITEMS 100
#define MAX_CAPACITY 1000

// 物品结构体
typedef struct {
    int weight;
    int value;
} Item;

// 0/1背包问题动态规划函数
int knapsack(int capacity, Item items[], int num_items) {
    // 创建一维数组dp，用于保存最优解
    int dp[MAX_CAPACITY + 1] = {0};

    // 动态规划计算最优解
    for (int i = 0; i < num_items; i++) {
        for (int j = capacity; j >= items[i].weight; j--) {
            int take_item = dp[j - items[i].weight] + items[i].value;
            int skip_item = dp[j];
            dp[j] = (take_item > skip_item) ? take_item : skip_item;
        }
    }

    // 返回最优解
    return dp[capacity];
}

int main() {
    // 创建物品数组
    Item items[] = {
        {2, 12},
        {1, 10},
        {3, 20},
        {2, 15}
    };
    int num_items = sizeof(items) / sizeof(items[0]);

    // 背包容量
    int capacity = 5;

    // 计算最优解并输出
    int max_value = knapsack(capacity, items, num_items);
    printf("背包问题最优解为：%d\n", max_value);

    return 0;
}