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.

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);
+	}
+
 }