#include <iostream>
#include <algorithm>
#include <vector>
struct Item {
int weight;
int value;
double ratio; // Value-to-weight ratio
};
bool compare(Item a, Item b) {
return a.ratio > b.ratio;
}
double fractionalKnapsack(int capacity, std::vector<Item>& items) {
std::sort(items.begin(), items.end(), compare);
double totalValue = 0.0;
for (const auto& item : items) {
if (capacity >= item.weight) {
totalValue += item.value;
capacity -= item.weight;
} else {
totalValue += (static_cast<double>(capacity) / item.weight) * item.value;
break;
}
}
return totalValue;
}
int main() {
int capacity;
std::cout << "Enter the knapsack capacity: ";
std::cin >> capacity;
int n;
std::cout << "Enter the number of items: ";
std::cin >> n;
std::vector<Item> items(n);
std::cout << "Enter the weight and value of each item:\n";
for (int i = 0; i < n; ++i) {
std::cin >> items[i].weight >> items[i].value;
items[i].ratio = static_cast<double>(items[i].value) / items[i].weight;
}
double maxValue = fractionalKnapsack(capacity, items);
std::cout << "Maximum value in Knapsack = " << maxValue << "\n";
return 0;
}