0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
Tags: java, datastructure, algorithms, dp
Published: 2022-07-20 14:45:00

You are given weights and values of **N** items, put these items in a knapsack of capacity **W** to get the maximum total value in the **knapsack**. Note that we have only one quantity of each item.
In other words, given two integer arrays **val[0..N-1]** and **wt[0..N-1]** which represent values and weights associated with **N** items respectively. Also given an integer **W** which represents knapsack capacity, find out the maximum value subset of **val[]** such that sum of the weights of this subset is smaller than or equal to **W**. You cannot break an item, **either pick the complete item or dont pick it** (0-1 property).

**Example 1**:

```
Input:
N = 3
W = 4
values[] = {1,2,3}
weight[] = {4,5,1}
Output: 3

```

**Solution**:
```java
class Solution 
{ 
    //Function to return max value that can be put in knapsack of capacity W.
    static int knapSack(int W, int wt[], int val[], int n) 
    { 
         // your code here 
         //This is similar to subset sum equals to target
         // this can be solved using backtracking 
         //i.e taking value at an index, or not taking it
         //lets optimize it with dp
         int dp[][] = new int[n][W+1];
         for(int row[]: dp){
             Arrays.fill(row,-1);
         }
         return solve(n-1,wt,val,W,dp); // starting from the last index hence n-1;
    } 
     public static int solve(int index, int[] w, int [] val, int target,int dp[][]){
        // base case
        if(index==0){
            //we have reached the first index, and in order for the value to be accepted
            //at this index, the weight of the value at i should be equal to target
            if(w[index]<=target) return val[index];
            return 0;
        }
        if(dp[index][target]!=-1) return dp[index][target];
        int take = 0;
        if(target>=w[index]){
            take = val[index]+ solve(index-1,w,val,target-w[index],dp);
        }
        int dontTake = 0+ solve(index-1,w,val,target,dp);
        return dp[index][target] =  Integer.max(take,dontTake);
    }
}
```
**Removing stack space of O(n) ie for n times stack will be created in worst case**

_Using tabulation approach (top down dp)_

```java
//tabulation appraoch : dp top down : tc O(n*W) space complexity : O(n*W) on stack space :)
class Solution 
{ 
    //Function to return max value that can be put in knapsack of capacity W.
    static int knapSack(int W, int wt[], int val[], int n) 
    { 
         // your code here 
         //This is similar to subset sum equals to target
         // this can be solved using backtracking 
         //i.e taking value at an index, or not taking it
         //lets optimize it with dp
         int dp[][] = new int[n][W+1];
        for(int i = wt[0];i<=W;i++){
            //it means that weight at index  0 should be less than or equals to 
            // target ie weigth W
            //so every time when the weigth is less than or equals to target(W) strore val[0] in dp[0][i] ;
            dp[0][i] = val[0];
        }
         for(int i =1;i<n;i++){
             for(int tar = 0;tar<=W;tar++){
                 int take =0;
                 if(tar>=wt[i]){
                    take = val[i]+dp[i-1][tar-wt[i]];
                 }
                 int dontTake = 0+ dp[i-1][tar];
                 dp[i][tar] = Integer.max(take,dontTake);
             }
         }
          return dp[n-1][W];
       
    } 
```

## Unbounded 0/1 Knapsack

**Note: Each item can be taken any number of times.**

```java
class Solution{
    static int knapSack(int N, int W, int val[], int wt[])
    {
        int dp[][] = new int[N][W+1];
        for(int row[]:dp){
            Arrays.fill(row,-1);
        }
        return maxProfit(N-1,W,val,wt,dp);
    }
    public static int maxProfit(int index, int W,int [] val, int w[],int dp[][]){
        if(index==0){
             //let say at index 0 val = 10 , w[index] = 3 and W =8 ,
            // now we can consider index 0 twice ,as 3*2 =6<=8
            ///hence for twice 2*val = 2*10 = 20 , hence return 20;
            //just convert the above logic in code;
            return (W/w[index])*val[index];
           
        }
        if(dp[index][W]!=-1) return dp[index][W];
        int take =0;// taki
ng the same index
        if(W>=w[index]){
            take = val[index] + maxProfit(index,W-w[index],val,w,dp);
        }
        int dontTake = 0 + maxProfit(index-1,W,val,w,dp);
        return dp[index][W] =  Integer.max(take,dontTake);
    }
}
```