1 files changed, 49 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java
new file mode 100644
index 0000000..f16fbc7
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java
@@ -0,0 +1,49 @@
+import java.util.Scanner;
+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[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) {
+        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();
+	}
+
+}