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)