Fractional Knapsack

 Fractional Knapsack

#include <stdio.h>

#include <stdlib.h>

typedef struct {

    double value;

    double weight;

} Item;

int compare(const void* a, const void* b) {

    Item* itemA = (Item*)a;

    Item* itemB = (Item*)b;

    double ratioA = itemA->value / itemA->weight;

    double ratioB = itemB->value / itemB->weight;

    if (ratioA > ratioB)

        return -1;

    else if (ratioA < ratioB)

        return 1;

    else

        return 0;

}

double fractionalKnapsack(int capacity, Item items[], int n) {

    qsort(items, n, sizeof(Item), compare);

    double totalValue = 0.0;

    int i;

    for (i = 0; i < n; i++) {

        if (items[i].weight <= capacity) {

            totalValue += items[i].value;

            capacity -= items[i].weight;

        } else {

            totalValue += (capacity / items[i].weight) * items[i].value;

            break;

        }

    }

    return totalValue;

}

int main() {

    int capacity = 50;

    Item items[] = {

        { 60, 10 },

        { 100, 20 },

        { 120, 30 }

    };

    int n = sizeof(items) / sizeof(items[0]);

    double maxValue = fractionalKnapsack(capacity, items, n);

    printf("Maximum value: %.2f\n", maxValue);

    return 0;

}