编辑代码

#include <stdio.h>
#include <stdlib.h>
#define MAX_ITEMS 5
typedef struct {
    int weight;
    int value;
    float valuePerWeight;
} Bean;
int compare(const void *a, const void *b) {
    float ratioA = ((Bean *)a)->valuePerWeight;
    float ratioB = ((Bean *)b)->valuePerWeight;
    return (ratioB > ratioA) ? 1 : -1;
}
int knapsackGreedy(Bean beans[], int n, int W) {
    qsort(beans, n, sizeof(Bean), compare);
    int totalValue = 0;
    int currentWeight = 0;
    for (int i = 0; i < n; i++) {
        if (currentWeight + beans[i].weight <= W) {
            currentWeight += beans[i].weight;
            totalValue += beans[i].value;
        }
    }
    return totalValue;
}
int main() {
    Bean beans[MAX_ITEMS] = {{100, 100}, {30, 90}, {60, 120}, {20, 80}, {50, 75}};
    int n = sizeof(beans) / sizeof(beans[0]);
    int W = 100;
    int result = knapsackGreedy(beans, n, W);
    printf("Maximum value in the knapsack (greedy): %d\n", result);
    return 0;
}