#include <stdio.h>
#include <stdlib.h>
struct Fruit {
char name[10];
int weight;
int value;
};
int compare(const void *a, const void *b) {
int ratioA = ((struct Fruit*)a)->value / ((struct Fruit*)a)->weight;
int ratioB = ((struct Fruit*)b)->value / ((struct Fruit*)b)->weight;
return ratioB - ratioA;
}
int greedyKnapsack(struct Fruit fruits[], int n, int capacity) {
qsort(fruits, n, sizeof(struct Fruit), compare);
int totalValue = 0;
int currentWeight = 0;
for (int i = 0; i < n; ++i) {
if (currentWeight + fruits[i].weight <= capacity) {
currentWeight += fruits[i].weight;
totalValue += fruits[i].value;
printf("%s(%dkg),", fruits[i].name, fruits[i].weight);
} else {
int remainingWeight = capacity - currentWeight;
int fraction = (remainingWeight * fruits[i].value) / fruits[i].weight;
totalValue += fraction;
printf("%s(%dkg部分),", fruits[i].name, remainingWeight);
break;
}
}
return totalValue;
}
int main() {
struct Fruit fruits[] = {
{"苹果", 15, 300},
{"香蕉", 18, 180},
{"橘子", 10, 150},
{"猕猴桃", 9, 270}
};
int n = sizeof(fruits) / sizeof(fruits[0]);
int capacity = 20;
int maxTotalValue = greedyKnapsack(fruits, n, capacity);
printf("\n背包中水果的总价值为:%d 元\n", maxTotalValue);
return 0;
}