编辑代码

#include <stdio.h>

// 定义物品结构
typedef struct {
    char name[10];
    int weight;
    int value;
}Fruit_info;

// 背包最大承重
#define MAX_WEIGHT 20
// 打印装水果的策略
void print_fruit(int dp[][MAX_WEIGHT + 1], Fruit_info items[], int items_size) {
    int i = items_size;
    int j = MAX_WEIGHT;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("装入 %s, 重量：%dkg, 价值：%d元\n", items[i - 1].name, items[i - 1].weight, items[i - 1].value);
            j -= items[i - 1].weight;
        }
        i--;
    }
}

// 动态规划求解最大价值
int solveKnapsack(Fruit_info items[], int items_size) {
    int dp[items_size + 1][MAX_WEIGHT + 1];

    for (int i = 0; i <= items_size; i++) {
        for (int w = 0; w <= MAX_WEIGHT; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            }
            else if (items[i - 1].weight <= w) {
                dp[i][w] = dp[i - 1][w]>(items[i - 1].value + dp[i - 1][w - items[i - 1].weight])?
                           dp[i - 1][w]:(items[i - 1].value + dp[i - 1][w - items[i - 1].weight]);
                //max(items[i - 1].value + dp[i - 1][w - items[i - 1].weight], dp[i - 1][w]);
            }
            else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    print_fruit(dp, items, items_size);

    return dp[items_size][MAX_WEIGHT];
}

int main() {
    Fruit_info items[] = {
        {"苹果", 15, 300},
        {"香蕉", 18, 180},
        {"橘子", 10, 150},
        {"猕猴桃", 9, 270}
    };

    int items_size = sizeof(items) / sizeof(items[0]);

    int count = solveKnapsack(items, items_size);

    printf("\n背包中装入水果的总价值最高为：%d元\n", count);

    return 0;
}