include <stdio.h>
include <stdlib.h>
// Structure to store each item’s weight, value, and value-to-weight ratio
typedef struct {
int weight;
int value;
double ratio;
} Item;
// Comparison function for sorting items by value-to-weight ratio in descending order
int compare(const void *a, const void *b) {
Item item1 = (Item)a;
Item item2 = (Item)b;
// Sort in descending order of ratio
if (item1->ratio < item2->ratio)
return 1;
else if (item1->ratio > item2->ratio)
return -1;
else
return 0;
}
double fractionalKnapsack(int N, int W_max, Item items) {
// Sorting items by value-to-weight ratio
qsort(items, N, sizeof(Item), compare);
double totalValue = 0.0;
int remainingCapacity = W_max;
for (int i = 0; i < N; i++) {
// If the item can be fully taken, take it
if (items[i].weight <= remainingCapacity) {
totalValue += items[i].value;
remainingCapacity -= items[i].weight;
}
// If only a fraction of the item can be taken, take the fraction
else {
totalValue += items[i].value * ((double) remainingCapacity / items[i].weight);
break; // Knapsack is full
}
}
return totalValue;
}
int main() {
int N, W_max;
scanf(“%d %d”, &N, &W_max);
// Create an array of items
Item *items = (Item*) malloc(N * sizeof(Item));
// Input item weights and values, and compute value-to-weight ratio
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; // Calculate ratio
}
// Call the function to solve the problem
double result = fractionalKnapsack(N, W_max, items);
// Print the result with the required precision
printf("%.2lf\n", result);
// Free allocated memory
free(items);
return 0;
}