Fractional Knapsack problem

#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;
}