From 42fe007dab117b7bf68ca8d3e8401dff606bcf85 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 7 Sep 2018 09:14:57 -0500 Subject: 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.--- .../sources/FractionalKnapsack.java | 82 +++++++++++++++++++--- .../tests/FractionalKnapsackTest.java | 70 ++++++++++++++++-- 2 files changed, 134 insertions(+), 18 deletions(-) (limited to 'AlgoDesignAndTechniqueEdxJava') 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); + } + } -- cgit v1.2.3