编辑代码

#include <stdio.h>
#include <string.h>
struct Fruit {
    char name[20];
    int weight;
    int value;
};
void optimizeBackpack(struct Fruit fruits[], int n, int capacity) {
    int dp[capacity + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= fruits[i].weight; j--) {
            dp[j] = dp[j] > dp[j - fruits[i].weight] + fruits[i].value ? dp[j] : dp[j - fruits[i].weight] + fruits[i].value;
        }
    }
    printf("背包最大价值: %d\n", dp[capacity]);
    printf("装入水果策略：\n");
    int remainCapacity = capacity;
    for (int i = n - 1; i >= 0; i--) {
        if (remainCapacity >= fruits[i].weight && dp[remainCapacity] == dp[remainCapacity - fruits[i].weight] + fruits[i].value) {
            printf("%s\n", fruits[i].name);
            remainCapacity -= fruits[i].weight;
        }
    }
}
int main() {
    struct Fruit fruits[] = {
        {"苹果", 15, 300},
        {"香蕉", 18, 180},
        {"橘子", 10, 150},
        {"猕猴桃", 9, 270}
    };
    int n = sizeof(fruits) / sizeof(fruits[0]);
    int capacity = 20;
    optimizeBackpack(fruits, n, capacity);
    return 0;
}