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

// Structure for an item
typedef struct {
    int weight;
    int value;
    double ratio; // value/weight
} Item;

// Comparator function for sorting items by ratio (descending order)
int compare(const void *a, const void *b) {
    double r1 = ((Item *)b)->ratio;
    double r2 = ((Item *)a)->ratio;
    return (r1 > r2) - (r1 < r2);
}

// Function to solve the Fractional Knapsack Problem
double fractionalKnapsack(int W, Item items[], int n) {
    // Sorting items based on value/weight ratio
    qsort(items, n, sizeof(Item), compare);

    double maxValue = 0.0; // Maximum value we can achieve
    int currentWeight = 0; // Current weight in knapsack

    for (int i = 0; i < n; i++) {
        // If the entire item can be picked
        if (currentWeight + items[i].weight <= W) {
            currentWeight += items[i].weight;
            maxValue += items[i].value;
        } 
        // If only a fraction of the item can be picked
        else {
            int remainingWeight = W - currentWeight;
            maxValue += items[i].ratio * remainingWeight;
            break; // Knapsack is full
        }
    }

    return maxValue;
}

// Driver code
int main() {
    int n, W;
    
    printf("Enter the number of items: ");
    scanf("%d", &n);
    
    Item items[n];

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

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

    double maxValue = fractionalKnapsack(W, items, n);
    printf("Maximum value in the knapsack = %.2f\n", maxValue);

    return 0;
}