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

public class KnapsackProb {

    public static void main(String[] args) {
        double[][] items = new double[][] { { 5, 3, 6, 12, 7 }, { 2, 3, 4, 7, 1 } };
        double[][] items2 = new double[][] { { 18, 15, 10 }, { 25, 24, 15 } };
        double[][] items3 = new double[][] { { 5, 4, 10, 7, 10, 4 }, { 9, 10, 12, 20, 18, 9 } };
        // knapsack(0,items2,21);
        knapsack(items, 21);
        // knapsack(items3,25);
    }

    public static void knapsack(double[][] items, double maxCapacity) {
        List<Double> sackOrdered = new ArrayList<Double>();
        List<Double> sack = new ArrayList<Double>();
        List<Integer> order = new ArrayList<Integer>();
        ArrayList<Integer> index = new ArrayList<Integer>();

        List<Data> listOfData = new ArrayList<>();

        int row = items.length;
        int col = items[0].length;

        // items[0][i] = weights //items[1][i]= values
        double[] weights = new double[col];
        double[] values = new double[col];
        double totalWeight = 0;
        double totalValue = 0;
        // System.out.println(row);
        // System.out.println(col);

        double ratio = 0.0;
        for (int j = 0; j < col; j++) {
            weights[j] = items[0][j];
            values[j] = items[1][j];
            ratio = values[j] / weights[j];
            listOfData.add(new Data(j,ratio));
            sackOrdered.add(ratio);
            index.add(j);
            // System.out.println(values[j]+" * "+ weights[j]);
        }

        for (Data data : listOfData) {
            System.out.println(data);
        }

        listOfData.sort(Comparator.comparingDouble(Data::getValue).reversed());

        System.out.println("\n-----After sorting");
        for (Data data : listOfData) {
            System.out.println(data);
        }

        int[] indexes = listOfData.stream().mapToInt(Data::getInitialIndex).toArray();
        System.out.println(Arrays.toString(indexes));

        // System.out.println(Arrays.toString(indexes));

        // System.out.println("after ordering "+sackOrdered);

        for (int j = 0; j < col; j++) {
            // System.out.println(items[i][j]);
            // weights[j] = items[0][j];
            // values[j] = items[1][j];
            // System.out.println(weights[j] + " //// "+values[j]);

            if (maxCapacity > 0) {

                sack.add(weights[indexes[j]]);
                order.add(indexes[j]);
                totalWeight = totalWeight + weights[indexes[j]];
                totalValue = totalValue + values[indexes[j]];

                // System.out.println("sack contents before checking the weight"+sack);
                /*
                 * System.out.println("order  "+order);
                 * System.out.println("totalWeight = "+totalWeight);
                 * System.out.println("totalValues = "+totalValue);
                 */

                if (totalWeight > maxCapacity) {
                    // sack.add(weights[j]);
                    // order.add(j);
                    sack.remove(sack.size() - 1);
                    order.remove(order.size() - 1);
                    totalWeight = totalWeight - weights[indexes[j]];
                    totalValue = totalValue - values[indexes[j]];

                    // System.out.println("sack contents after checking the weight"+sack);
                    // System.out.println("order "+order);
                    // System.out.println("totalWeight = "+totalWeight);
                    // System.out.println("totalValues = "+totalValue);

                } else {

                }

            }

        }
        System.out.println("order  " + order);
        System.out.println("totalWeight = " + totalWeight);
        System.out.println("totalValues = " + totalValue);
    }

}

class Data {
    private int initialIndex;
    private double value;

    public Data(int initialIndex, double value) {
        super();
        this.initialIndex = initialIndex;
        this.value = value;
    }

    public double getValue() {
        return value;
    }

    public int getInitialIndex() {
        return initialIndex;
    }

    @Override
    public String toString() {
        return "Data(initialIndex= " + initialIndex + ", value= " + value + ")";
    }
}