From 29e054f5ebf164d53319c0bdb348db421f98b942 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 7 Sep 2018 09:34:28 -0500 Subject: Fractional Knapsack done! Very rewarding, lots of fun. I'm glad I wasn't lazy, and did the work of stress testing, which really didn't put much stress, but helped me pinpoint the bug. Plus I think stress testing will be useful down the road, very good technique.--- .../sources/FractionalKnapsack.java | 69 +++++++++++----------- 1 file changed, 34 insertions(+), 35 deletions(-) diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java index 49ec02b..3aa823f 100644 --- a/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java +++ b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java @@ -24,41 +24,41 @@ public class FractionalKnapsack { } public static void main(String[] args) { - 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(); +// 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; +// } // } -// System.out.println(getOptimalValue(capacity, values, weights)); + 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) { @@ -103,7 +103,6 @@ public class FractionalKnapsack { weights[j] = weights[j] - tempWeight; capacity = capacity - tempWeight; } - return totalValue; } } -- cgit v1.2.3