编辑代码

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double weight;
    double value;
    double ratio; // 单位重量价值
} Item;

int compare(const void *a, const void *b) {
    Item *item1 = (Item *)a;
    Item *item2 = (Item *)b;
    return (item2->ratio - item1->ratio) > 0 ? 1 : -1;
}

double fractionalKnapsack(Item items[], int n, double capacity) {
    qsort(items, n, sizeof(Item), compare);

    double totalValue = 0.0;

    for (int i = 0; i < n; i++) {
        if (capacity >= items[i].weight) {
            totalValue += items[i].value;
            capacity -= items[i].weight;
        } else {
            totalValue += items[i].ratio * capacity;
            break;
        }
    }

    return totalValue;
}

int main() {
    int n;
    double capacity;

    printf("Enter number of items: ");
    scanf("%d", &n);

    Item items[n];

    printf("Enter weights and values of items:\n");
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &items[i].weight, &items[i].value);
        items[i].ratio = items[i].value / items[i].weight;
    }

    printf("Enter the capacity of the knapsack: ");
    scanf("%lf", &capacity);

    double max_value = fractionalKnapsack(items, n, capacity);
    printf("The maximum value that can be obtained is: %.2lf\n", max_value);

    return 0;
}