import java.util.Arrays;

import java.util.Comparator;

import java.util.Scanner;

class Item {

    int id;

    int weight;

    int profit;

    double cost;

    public Item(int id, int weight, int profit) {

        this.id = id;

        this.weight = weight;

        this.profit = profit;

        this.cost = (double) profit / weight;

    }

}

public class FractionalKnapsack {

    public static double fractionalKnapsack(Item[] items, int capacity, float[] solutionVector) {

        Arrays.sort(items, Comparator.comparingDouble(item -> -item.cost));

        double totalProfit = 0.0;

        for (Item item : items) {

            if (capacity == 0) {

                break;

            }

            if (item.weight <= capacity) {

                totalProfit += item.profit;

                capacity -= item.weight;

                solutionVector[item.id - 1] = 1.0f;

            } else {

                float fraction = (float) capacity / item.weight;

                totalProfit += item.profit * fraction;

                solutionVector[item.id - 1] = fraction;

                capacity = 0;

            }

        }

        return totalProfit;

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of items: ");

        int n = scanner.nextInt();

        System.out.print("Enter the capacity of the knapsack: ");

        int capacity = scanner.nextInt();

        Item[] items = new Item[n];

        float[] solutionVector = new float[n];

        for (int i = 0; i < n; i++) {

            System.out.print("Enter weight and profit of item " + (i + 1) + ": ");

            int weight = scanner.nextInt();

            int profit = scanner.nextInt();

            items[i] = new Item(i + 1, weight, profit);

            solutionVector[i] = 0.0f;

        }

        double maxProfit = fractionalKnapsack(items, capacity, solutionVector);

        System.out.printf("Maximum profit in Knapsack = %.2f\n", maxProfit);

        System.out.print("Solution vector (ID: fraction included): ");

        for (int i = 0; i < n; i++) {

            System.out.printf(" %d: %.2f ", items[i].id, solutionVector[i]);

        }

        System.out.println();

        

    }

}