import java.util.Arrays; import java.util.Scanner; import java.util.concurrent.ThreadLocalRandom; import java.util.stream.IntStream; public class FractionalKnapsack { public static double getOptimalValue(int capacity, int[] values, int[] weights) { double totalValue = 0; int tempWeight = 0; int[] sortedAscendingIndex = getSortedIndexArray(values, weights); for (int i = sortedAscendingIndex.length - 1; i >= 0; i--) { if (capacity == 0) return totalValue; if (weights[sortedAscendingIndex[i]] < capacity) tempWeight = weights[sortedAscendingIndex[i]]; else tempWeight = capacity; totalValue = totalValue + tempWeight * ((double) values[sortedAscendingIndex[i]] / weights[sortedAscendingIndex[i]]); capacity = capacity - tempWeight; } return totalValue; } public static void main(String[] args) { // int weight = 50; // int numOfItems = 3; // // while (true) { // int[] values = new int[numOfItems]; // int[] weights = new int[numOfItems]; // for (int i = 0; i < weights.length; i++) { // values[i] = ThreadLocalRandom.current().nextInt(0, 50); // weights[i] = ThreadLocalRandom.current().nextInt(1, 50); // } // int[] values1 = values.clone(); // int[] values2 = values.clone(); // int[] weights1 = weights.clone(); // int[] weights2 = weights.clone(); // double result1 = getOptimalValue(weight, values1, weights1); // double result2 = getOptimalValueNaive(weight, values2, weights2); // // if (result1!=result2) { // System.out.println(Arrays.toString(values)); // System.out.println(Arrays.toString(weights)); // System.out.println(result1); // System.out.println(result2); // break; // } // } Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int capacity = scanner.nextInt(); int[] values = new int[n]; int[] weights = new int[n]; for (int i = 0; i < n; i++) { values[i] = scanner.nextInt(); weights[i] = scanner.nextInt(); } System.out.println(getOptimalValue(capacity, values, weights)); } public static int[] getSortedIndexArray(int[] values, int[] weights) { // https://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-after-sorting double[] valueWeightRatio = new double[values.length]; for (int i = 0; i < values.length; i++) { valueWeightRatio[i] = (double) values[i] / weights[i]; } return IntStream.range(0, values.length).boxed() .sorted((i, j) -> Double.compare(valueWeightRatio[i], valueWeightRatio[j])).mapToInt(ele -> ele) .toArray(); } public static int getBestItem(int[] values, int[] weights) { double maxValuePerWeight = 0; int bestItem = 0; for (int i = 0; i < weights.length; i++) { if (weights[i] > 0) { if ((double) values[i] / weights[i] > maxValuePerWeight) { maxValuePerWeight = (double) values[i] / weights[i]; bestItem = i; } } } return bestItem; } public static double getOptimalValueNaive(int capacity, int[] values, int[] weights) { double totalValue = 0; int tempWeight = 0; for (int i = 0; i < weights.length; i++) { if (capacity == 0) return totalValue; int j = getBestItem(values, weights); if (weights[j] < capacity) tempWeight = weights[j]; else tempWeight = capacity; totalValue = totalValue + tempWeight * ((double) values[j] / weights[j]); weights[j] = weights[j] - tempWeight; capacity = capacity - tempWeight; } return totalValue; } }