编辑代码

#include <stdio.h>

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

void printStrategy(int dp[4][21], Fruit fruits[]) {
    int i = 3;
    int j = 20;

    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("装入%s\n", fruits[i].name);
            j -= fruits[i].weight;
        }
        i--;
    }

    if (j > 0)
        printf("装入%s\n", fruits[i].name);
}

void optimizeBackpack(Fruit fruits[]) {
    int dp[4][21] = {0};

    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 20; j++) {
            if (fruits[i].weight <= j)
                dp[i][j] = (fruits[i].value + dp[i - 1][j - fruits[i].weight] > dp[i - 1][j])
                               ? fruits[i].value + dp[i - 1][j - fruits[i].weight]
                               : dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j];
        }
    }

    printf("装水果的策略如下：\n");
    printStrategy(dp, fruits);
}

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

    optimizeBackpack(fruits);

    return 0;
}