summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-09-07 09:14:57 -0500
committerHaidong Ji2018-09-07 09:14:57 -0500
commit42fe007dab117b7bf68ca8d3e8401dff606bcf85 (patch)
tree7635246e5658062122318ce69729bfe6fe0abda0
parentbddfc348f5dbf69c004049f74939f2c837cca945 (diff)
Stress tested according to week 1 pdf, found and fixed bug!
The bug was simple: I picked the index of the sortedAscendingIndex, not its value in weight comparison.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java82
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java70
2 files changed, 134 insertions, 18 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java
index f16fbc7..49ec02b 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java
@@ -1,4 +1,6 @@
+import java.util.Arrays;
import java.util.Scanner;
+import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.IntStream;
public class FractionalKnapsack {
@@ -10,7 +12,7 @@ public class FractionalKnapsack {
for (int i = sortedAscendingIndex.length - 1; i >= 0; i--) {
if (capacity == 0)
return totalValue;
- if (weights[i] < capacity)
+ if (weights[sortedAscendingIndex[i]] < capacity)
tempWeight = weights[sortedAscendingIndex[i]];
else
tempWeight = capacity;
@@ -22,16 +24,41 @@ public class FractionalKnapsack {
}
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));
+ 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) {
@@ -46,4 +73,37 @@ public class FractionalKnapsack {
.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;
+ }
}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java b/AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java
index 54dd4f7..6215219 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/FractionalKnapsackTest.java
@@ -5,27 +5,83 @@ import org.junit.jupiter.api.Test;
class FractionalKnapsackTest {
@Test
- void test1() {
+ void testGetSortedIndexArray() {
+ 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 testGetBestItem1() {
+ int[] values = new int[] { 60, 100, 120 };
+ int[] weights = new int[] { 20, 50, 30 };
+ assertEquals(2, FractionalKnapsack.getBestItem(values, weights));
+ }
+
+ @Test
+ void testGetBestItem2() {
+ int[] values = new int[] { 500 };
+ int[] weights = new int[] { 30 };
+ assertEquals(0, FractionalKnapsack.getBestItem(values, weights));
+ }
+
+ @Test
+ void testNaive1() {
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));
+ assertEquals(180.0000, FractionalKnapsack.getOptimalValueNaive(capacity, values, weights));
}
+
@Test
- void test2() {
+ void testNaive2() {
+ int[] values = new int[] { 500 };
+ int[] weights = new int[] { 30 };
+ int capacity = 10;
+ assertEquals(166.6667, FractionalKnapsack.getOptimalValueNaive(capacity, values, weights), 0.0001);
+ }
+
+ @Test
+ void test1() {
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));
+ int capacity = 50;
+ assertEquals(180.0000, FractionalKnapsack.getOptimalValue(capacity, values, weights));
}
+
@Test
- void test3() {
- int[] values = new int[] { 500};
+ void test2() {
+ int[] values = new int[] { 500 };
int[] weights = new int[] { 30 };
int capacity = 10;
assertEquals(166.6667, FractionalKnapsack.getOptimalValue(capacity, values, weights), 0.0001);
}
+ @Test
+ void testStress1() {
+ int[] values = new int[] { 11, 43, 4, 35, 21 };
+ int[] weights = new int[] { 45, 11, 40, 19, 10 };
+ int capacity = 50;
+ assertEquals(101.4444, FractionalKnapsack.getOptimalValue(capacity, values, weights), 0.0001);
+ }
+
+ @Test
+ void testStress2() {
+ int[] values = new int[] { 11, 43, 4, 35, 21 };
+ int[] weights = new int[] { 45, 11, 40, 19, 10 };
+ int capacity = 50;
+ assertEquals(101.4444, FractionalKnapsack.getOptimalValueNaive(capacity, values, weights), 0.0001);
+ }
+
+ @Test
+ void testStress3() {
+ int[] values = new int[] { 44, 26, 31 };
+ int[] weights = new int[] { 6, 28, 38 };
+ int capacity = 50;
+ assertEquals(83.0526, FractionalKnapsack.getOptimalValue(capacity, values, weights), 0.0001);
+ }
+
}