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**:

```
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)*

```
//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.**

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

## Top comments (0)