summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-09-05 22:19:43 -0500
committerHaidong Ji2018-09-05 22:19:43 -0500
commitbddfc348f5dbf69c004049f74939f2c837cca945 (patch)
tree8dae6c5c044ffe167cca80c465582af0d62e3641
parent2a23f32bd6db02252509d0d9fdddc0b44b10056a (diff)
Buggy FractionalKnapsack for now. Work on a python version first.
I may need to do an exhaustive testing.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java49
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java31
2 files changed, 80 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();
+ }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java b/AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java
new file mode 100644
index 0000000..54dd4f7
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java
@@ -0,0 +1,31 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class FractionalKnapsackTest {
+
+ @Test
+ void test1() {
+ int[] values = new int[] { 60, 100, 120 };
+ int[] weights = new int[] { 20, 50, 30 };
+ int capacity = 50;
+ assertEquals(180.0000, FractionalKnapsack.getOptimalValue(capacity, values, weights));
+ }
+
+ @Test
+ void test2() {
+ int[] values = new int[] { 60, 100, 120 };
+ int[] weights = new int[] { 20, 50, 30 };
+ int[] sortedIndexArray = new int[] { 1, 0, 2 };
+ assertArrayEquals(sortedIndexArray, FractionalKnapsack.getSortedIndexArray(values, weights));
+ }
+
+ @Test
+ void test3() {
+ int[] values = new int[] { 500};
+ int[] weights = new int[] { 30 };
+ int capacity = 10;
+ assertEquals(166.6667, FractionalKnapsack.getOptimalValue(capacity, values, weights), 0.0001);
+ }
+
+}