//FractionalKnapsackDemo.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Item
{
    public double weight;
    public double value;
    public double fraction;

    Item
    (
        double itemWeight,
        double itemValue
    )
    {
        weight = itemWeight;
        value = itemValue;
        fraction = 1.0;
    }
}

class ItemRatioComparator implements Comparator<Item>
{
    public int compare
    (
        Item item1,
        Item item2
    )
    {
        double item1Ratio = item1.value / item1.weight;
        double item2Ratio = item2.value / item2.weight;
        if (item1Ratio < item2Ratio)
        {
            return 1;
        }
        else if (item1Ratio > item2Ratio)
        {
            return -1;
        }
        return 0;
    }
}

class Knapsack
{
    private double maxWeight;
    private ArrayList<Item> items;

    Knapsack(double maximumWeight)
    {
        maxWeight = maximumWeight;
        items = new ArrayList<Item>();
    }

    public ArrayList<Item> getItems()
    {
        return this.items;
    }

    public double getMaxWeight()
    {
        return maxWeight;
    }

    public static Knapsack fractionalKnapsack
    (
        Item[] availableItems,
        double maxWeight
    )
    {
        // Sort the items in descending order based on value/weight
        Arrays.sort(availableItems, new ItemRatioComparator());

        // Initialize a new knapsack to hold items
        Knapsack knapsack = new Knapsack(maxWeight);

        double remaining = maxWeight;
        for (Item item : availableItems)
        {
            // Check if the full item can fit into the knapsack or
            // only a fraction
            if (item.weight <= remaining)
            {
                // The full item will fit
                knapsack.getItems().add(item);
                remaining -= item.weight;
            }
            else if (remaining > 0)
            {
                // Only a fractional part of the item will fit. Add that
                // fraction of the item, and then exit.
                item.fraction = remaining / item.weight;
                knapsack.getItems().add(item);
                break;
            }
        }

        return knapsack;
    }
}

public class FractionalKnapsackDemo
{
    public static void main(String[] args)
    {
        // Create an ArrayList of available items
        Item[] availableItems =
        {
            new Item(6.0, 25.0),
            new Item(8.0, 42.0),
            new Item(12.0, 60.0),
            new Item(18.0, 95.0)
        };

        // Prompt for the knapsack's maximum weight
        Scanner scnr = new Scanner(System.in);
        System.out.print("Enter maximum weight the knapsack can hold: ");
        double maxWeight = scnr.nextDouble();

        Knapsack knapsack = Knapsack.fractionalKnapsack
                            (
                                availableItems,
                                maxWeight
                            );

        // Show the objects in the knapsack
        System.out.println("Objects in knapsack");
        int i = 1;
        double sumWeight = 0.0;
        double sumValue = 0.0;
        for (Item item : knapsack.getItems())
        {
            sumWeight += item.weight * item.fraction;
            sumValue += item.value * item.fraction;
            System.out.printf
            (
                "%d: %.1f of weight %.1f, value %.1f%n",
                i,
                item.fraction,
                item.weight,
                item.value * item.fraction
            );
            i++;
        }
        System.out.println();

        System.out.printf
        (
            "Total weight of items in knapsack: %d%n",
            (int) sumWeight
        );
        System.out.printf
        (
            "Total value of items in knapsack: %d%n",
            (int) sumValue
        );
    }
}