Java Program for 0-1 Knapsack Problem using Dynamic Programming
Memoization Approach for 0/1 Knapsack Problem:
If we get a subproblem the first time, we can solve this problem by creating a 2-D array that can store a particular state (n, w). Now if we come across the same state (n, w) again instead of calculating it in exponential complexity we can directly return its result stored in the table in constant time.
Below is the implementation of the above approach:
Java
// Here is the top-down approach of // dynamic programming import java.io.*; class GFG { // 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) { // Base condition if (n == 0 || W == 0 ) return 0 ; if (dp[n][W] != - 1 ) return dp[n][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); 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)); } static int knapSack( int W, int wt[], int val[], int N) { // 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 ; return knapSackRec(W, wt, val, N, dp); } // Driver Code public static void main(String[] args) { int profit[] = { 60 , 100 , 120 }; int weight[] = { 10 , 20 , 30 }; int W = 50 ; int N = profit.length; System.out.println(knapSack(W, weight, profit, N)); } } // This Code is contributed By FARAZ AHMAD |
220
Time Complexity: O(N * W). As redundant calculations of states are avoided.
Auxiliary Space: O(N * W) + O(N). The use of a 2D array data structure for storing intermediate states and O(N) auxiliary stack space(ASS) has been used for recursion stack
Bottom-up Approach for 0/1 Knapsack Problem:
Since subproblems are evaluated again, this problem has Overlapping Sub-problems property. So the 0/1 Knapsack problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, re-computation of the same subproblems can be avoided by constructing a temporary array K[][] in a bottom-up manner.
Below is the implementation of the above approach:
Java
// A Dynamic Programming based solution // for 0-1 Knapsack problem import java.io.*; class Knapsack { // 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) { 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]; } } return K[n][W]; } // Driver code public static void main(String args[]) { int profit[] = new int [] { 60 , 100 , 120 }; int weight[] = new int [] { 10 , 20 , 30 }; int W = 50 ; int n = profit.length; System.out.println(knapSack(W, weight, profit, n)); } } /*This code is contributed by Rajat Mishra */ |
220
Time Complexity: O(N * W). where ‘N’ is the number of elements and ‘W’ is capacity.
Auxiliary Space: O(N * W). The use of a 2-D array of size ‘N*W’.
Space optimized Approach for 0/1 Knapsack Problem using Dynamic Programming:
For calculating the current row of the dp[] array we require only previous row, but if we start traversing the rows from right to left then it can be done with a single row only.
Below is the implementation of the above approach:
Java
// Java program for the above approach import java.util.*; class GFG { static int knapSack( int W, int wt[], int val[], int n) { // Making and initializing dp array int [] dp = new int [W + 1 ]; for ( int i = 1 ; i < n + 1 ; i++) { for ( int w = W; w >= 0 ; w--) { if (wt[i - 1 ] <= w) // Finding the maximum value dp[w] = Math.max(dp[w], dp[w - wt[i - 1 ]] + val[i - 1 ]); } } // Returning the maximum value of knapsack return dp[W]; } // Driver code public static void main(String[] args) { int profit[] = { 60 , 100 , 120 }; int weight[] = { 10 , 20 , 30 }; int W = 50 ; int n = profit.length; System.out.print(knapSack(W, weight, profit, n)); } } // This code is contributed by gauravrajput1 |
220
Time Complexity: O(N * W). As redundant calculations of states are avoided
Auxiliary Space: O(W) As we are using a 1-D array instead of a 2-D array
Please refer complete article on Dynamic Programming | Set 10 ( 0-1 Knapsack Problem) for more details!
Java Program 0-1 Knapsack Problem
Write a Java program for a given N items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.
Examples:
Input: N = 3, W = 4, profit[] = {1, 2, 3}, weight[] = {4, 5, 1}
Output: 3
Explanation: There are two items which have weight less than or equal to 4. If we select the item with weight 4, the possible profit is 1. And if we select the item with weight 1, the possible profit is 3. So the maximum possible profit is 3. Note that we cannot put both the items with weight 4 and 1 together as the capacity of the bag is 4.Input: N = 3, W = 3, profit[] = {1, 2, 3}, weight[] = {4, 5, 6}
Output: 0