Formatted with Google Java Formatter

github-actions · github-actions · commit f981a2b979a3 · 2021-09-17T17:03:36.000Z
diff --git a/DynamicProgramming/BruteForceKnapsack.java b/DynamicProgramming/BruteForceKnapsack.java
@@ -4,40 +4,38 @@
 of 0-1 Knapsack problem */
 public class BruteForceKnapsack {
 
-	// A utility function that returns
-	// maximum of two integers
-	static int max(int a, int b) {
-		return (a > b) ? a : b;
-	}
+  // A utility function that returns
+  // maximum of two integers
+  static int max(int a, int b) {
+    return (a > b) ? a : b;
+  }
 
-	// Returns the maximum value that
-	// can be put in a knapsack of
-	// capacity W
-	static int knapSack(int W, int wt[], int val[], int n) {
-		// Base Case
-		if (n == 0 || W == 0)
-			return 0;
+  // Returns the maximum value that
+  // can be put in a knapsack of
+  // capacity W
+  static int knapSack(int W, int wt[], int val[], int n) {
+    // Base Case
+    if (n == 0 || W == 0) return 0;
 
-		// If weight of the nth item is
-		// more than Knapsack capacity W,
-		// then this item cannot be included
-		// in the optimal solution
-		if (wt[n - 1] > W)
-			return knapSack(W, wt, val, n - 1);
+    // If weight of the nth item is
+    // more than Knapsack capacity W,
+    // then this item cannot be included
+    // in the optimal solution
+    if (wt[n - 1] > W) return knapSack(W, wt, val, n - 1);
 
-		// Return the maximum of two cases:
-		// (1) nth item included
-		// (2) not included
-		else
-			return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
-	}
+    // Return the maximum of two cases:
+    // (1) nth item included
+    // (2) not included
+    else
+      return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
+  }
 
-	// Driver code
-	public static void main(String args[]) {
-		int val[] = new int[] { 60, 100, 120 };
-		int wt[] = new int[] { 10, 20, 30 };
-		int W = 50;
-		int n = val.length;
-		System.out.println(knapSack(W, wt, val, n));
-	}
+  // Driver code
+  public static void main(String args[]) {
+    int val[] = new int[] {60, 100, 120};
+    int wt[] = new int[] {10, 20, 30};
+    int W = 50;
+    int n = val.length;
+    System.out.println(knapSack(W, wt, val, n));
+  }
 }
diff --git a/DynamicProgramming/DyanamicProgrammingKnapsack.java b/DynamicProgramming/DyanamicProgrammingKnapsack.java
@@ -3,37 +3,34 @@
 // A Dynamic Programming based solution
 // for 0-1 Knapsack problem
 public class DyanamicProgrammingKnapsack {
-	static int max(int a, int b) {
-		return (a > b) ? a : b;
-	}
+  static int max(int a, int b) {
+    return (a > b) ? a : b;
+  }
 
-	// Returns the maximum value that can
-	// be put in a knapsack of capacity W
-	static int knapSack(int W, int wt[], int val[], int n) {
-		int i, w;
-		int K[][] = new int[n + 1][W + 1];
+  // Returns the maximum value that can
+  // be put in a knapsack of capacity W
+  static int knapSack(int W, int wt[], int val[], int n) {
+    int i, w;
+    int K[][] = new int[n + 1][W + 1];
 
-		// Build table K[][] in bottom up manner
-		for (i = 0; i <= n; i++) {
-			for (w = 0; w <= W; w++) {
-				if (i == 0 || w == 0)
-					K[i][w] = 0;
-				else if (wt[i - 1] <= w)
-					K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
-				else
-					K[i][w] = K[i - 1][w];
-			}
-		}
+    // Build table K[][] in bottom up manner
+    for (i = 0; i <= n; i++) {
+      for (w = 0; w <= W; w++) {
+        if (i == 0 || w == 0) K[i][w] = 0;
+        else if (wt[i - 1] <= w) K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
+        else K[i][w] = K[i - 1][w];
+      }
+    }
 
-		return K[n][W];
-	}
+    return K[n][W];
+  }
 
-	// Driver code
-	public static void main(String args[]) {
-		int val[] = new int[] { 60, 100, 120 };
-		int wt[] = new int[] { 10, 20, 30 };
-		int W = 50;
-		int n = val.length;
-		System.out.println(knapSack(W, wt, val, n));
-	}
+  // Driver code
+  public static void main(String args[]) {
+    int val[] = new int[] {60, 100, 120};
+    int wt[] = new int[] {10, 20, 30};
+    int W = 50;
+    int n = val.length;
+    System.out.println(knapSack(W, wt, val, n));
+  }
 }
diff --git a/DynamicProgramming/MemoizationTechniqueKnapsack.java b/DynamicProgramming/MemoizationTechniqueKnapsack.java
@@ -1,59 +1,56 @@
 package DynamicProgramming;
-// Here is the top-down approach of 
+// Here is the top-down approach of
 // dynamic programming
 public class MemoizationTechniqueKnapsack {
 
-//A utility function that returns 
-//maximum of two integers    
-	static int max(int a, int b) {
-		return (a > b) ? a : b;
-	}
+  // A utility function that returns
+  // maximum of two integers
+  static int max(int a, int b) {
+    return (a > b) ? a : b;
+  }
 
-//Returns the value of maximum profit  
-	static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) {
+  // Returns the value of maximum profit
+  static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) {
 
-		// Base condition
-		if (n == 0 || W == 0)
-			return 0;
+    // Base condition
+    if (n == 0 || W == 0) return 0;
 
-		if (dp[n][W] != -1)
-			return dp[n][W];
+    if (dp[n][W] != -1) return dp[n][W];
 
-		if (wt[n - 1] > W)
+    if (wt[n - 1] > W)
 
-			// Store the value of function call
-			// stack in table before return
-			return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);
+      // Store the value of function call
+      // stack in table before return
+      return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);
+    else
 
-		else
+      // Return value of table after storing
+      return dp[n][W] =
+          max(
+              (val[n - 1] + knapSackRec(W - wt[n - 1], wt, val, n - 1, dp)),
+              knapSackRec(W, wt, val, n - 1, dp));
+  }
 
-			// Return value of table after storing
-			return dp[n][W] = max((val[n - 1] + knapSackRec(W - wt[n - 1], wt, val, n - 1, dp)),
-					knapSackRec(W, wt, val, n - 1, dp));
-	}
+  static int knapSack(int W, int wt[], int val[], int N) {
 
-	static int knapSack(int W, int wt[], int val[], int N) {
+    // Declare the table dynamically
+    int dp[][] = new int[N + 1][W + 1];
 
-		// Declare the table dynamically
-		int dp[][] = new int[N + 1][W + 1];
+    // Loop to initially filled the
+    // table with -1
+    for (int i = 0; i < N + 1; i++) for (int j = 0; j < W + 1; j++) dp[i][j] = -1;
 
-		// Loop to initially filled the
-		// table with -1
-		for (int i = 0; i < N + 1; i++)
-			for (int j = 0; j < W + 1; j++)
-				dp[i][j] = -1;
+    return knapSackRec(W, wt, val, N, dp);
+  }
 
-		return knapSackRec(W, wt, val, N, dp);
-	}
+  // Driver Code
+  public static void main(String[] args) {
+    int val[] = {60, 100, 120};
+    int wt[] = {10, 20, 30};
 
-//Driver Code
-	public static void main(String[] args) {
-		int val[] = { 60, 100, 120 };
-		int wt[] = { 10, 20, 30 };
+    int W = 50;
+    int N = val.length;
 
-		int W = 50;
-		int N = val.length;
-
-		System.out.println(knapSack(W, wt, val, N));
-	}
+    System.out.println(knapSack(W, wt, val, N));
+  }
 }
