编辑代码

#include <stdio.h>

struct Fruit {
    char name[20];
    int weight;
    int value;
};

// 计算最大总价值的函数
void knapsack(struct Fruit fruits[], int n, int capacity) {
    int dp[n + 1][capacity + 1];

    for (int i = 0; i <= n; ++i) {
        for (int w = 0; w <= capacity; ++w) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (fruits[i - 1].weight <= w) {
                dp[i][w] = (fruits[i - 1].value + dp[i - 1][w - fruits[i - 1].weight] > dp[i - 1][w]) ? 
                            (fruits[i - 1].value + dp[i - 1][w - fruits[i - 1].weight]) : dp[i - 1][w];
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // 回溯找到装水果的具体策略
    int i = n, w = capacity;
    while (i > 0 && w > 0) {
        if (dp[i][w] != dp[i - 1][w]) {
            printf("装入 %s，重量：%dkg，价值：%d\n", fruits[i - 1].name, fruits[i - 1].weight, fruits[i - 1].value);
            w -= fruits[i - 1].weight;
        }
        --i;
    }
}

int main() {
    struct Fruit fruits[] = {{"苹果", 15, 300}, {"香蕉", 18, 180}, {"橘子", 10, 150}, {"猕猴桃", 9, 270}};
    int n = sizeof(fruits) / sizeof(fruits[0]);
    int capacity = 20;

    printf("装水果的策略如下：\n");
    knapsack(fruits, n, capacity);

    return 0;
}