frackanp.cpp

#include <iostream>
using namespace std;

class Item {
public:
    int weight, value;
    float ratio;

    void set(int w, int v) {
        weight = w;
        value = v;
        ratio = (float)v / w;
    }
};

void fractionalKnapsack(int n, int capacity, Item *items) {
    // Sort by ratio in descending order
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (items[i].ratio < items[j].ratio) {
                Item temp = items[i];
                items[i] = items[j];
                items[j] = temp;
            }
        }
    }

    float totalValue = 0;
    int remaining = capacity;

    for (int i = 0; i < n && remaining > 0; i++) {
        if (items[i].weight <= remaining) {
            totalValue += items[i].value;
            remaining -= items[i].weight;
        } else {
            totalValue += items[i].ratio * remaining;
            break;
        }
    }

    cout << "Maximum value in knapsack: " << totalValue << endl;
}

int main() {
    int n, capacity;
    cout << "Enter number of items: ";
    cin >> n;
    cout << "Enter knapsack capacity: ";
    cin >> capacity;

    Item* items = new Item[n];

    cout << "Enter weight and value of each item:\n";
    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;
        items[i].set(w, v);
    }

    fractionalKnapsack(n, capacity, items);

    delete[] items;
    return 0;
}