diff options
author | Haidong Ji | 2018-09-07 09:14:57 -0500 |
---|---|---|
committer | Haidong Ji | 2018-09-07 09:14:57 -0500 |
commit | 42fe007dab117b7bf68ca8d3e8401dff606bcf85 (patch) | |
tree | 7635246e5658062122318ce69729bfe6fe0abda0 /AlgoDesignAndTechniqueEdxJava/sources | |
parent | bddfc348f5dbf69c004049f74939f2c837cca945 (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.
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java | 82 |
1 files changed, 71 insertions, 11 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; + } } |