编辑代码

#include <stdio.h>

#define MAX_WEIGHT 20  // 背包承重
#define FRUIT_NUM 4    // 水果种类数

typedef struct {
    char name[10];  // 水果名称
    int weight;     // 水果重量
    int value;      // 水果价值
} Fruit;

void printStrategy(int dp[FRUIT_NUM][MAX_WEIGHT + 1], Fruit fruits[FRUIT_NUM]) {
    int weight = MAX_WEIGHT;
    for (int i = FRUIT_NUM - 1; i >= 0; i--) {
        if (dp[i][weight] != dp[i - 1][weight]) {
            printf("装入水果 %s\n", fruits[i].name);
            weight -= fruits[i].weight;
        }
    }
}

void knapsack(Fruit fruits[FRUIT_NUM]) {
    int dp[FRUIT_NUM][MAX_WEIGHT + 1] = {0};

    // 动态规划求解最优值
    for (int i = 0; i < FRUIT_NUM; i++) {
        for (int j = 1; j <= MAX_WEIGHT; j++) {
            if (fruits[i].weight <= j) {
                int value1 = dp[i - 1][j];
                int value2 = dp[i - 1][j - fruits[i].weight] + fruits[i].value;
                dp[i][j] = (value1 > value2) ? value1 : value2;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    printf("装背包的策略为：\n");
    printStrategy(dp, fruits);
    printf("背包的总价值为：%d\n", dp[FRUIT_NUM - 1][MAX_WEIGHT]);
}

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

    knapsack(fruits);

    return 0;
}