Question: Given weights and profits of n items, put these items in a knapsack of capacity W to get the maximum total profit.

0-1 property:  You can either pick the item or not. Also you have only one copy of each item.

Let’s solve this question first using brute force approach.

As the question says, we can either pick the item or not, hence we have 2 options:

• Pick the ith item if possible, update current profit by adding the profit of this item in it. Finally go for the rest items.
• Don’t pick ith item and keep going for the rest ones without any update in the current profit.

It’s clearly a recursive function with two base case conditions:

• Return if we don’t have any item left in the array
• Return if the knapsack is full

Input:

n: size of weight and profit array

k: capacity of knapsack

Next each n line contains two variable weight[i] and profit[i]

( items are given in ascending order by their weight )

Implemented code in C++:

#include<bits/stdc++.h>
using namespace std;
int maxProfit(int k,vector<int>& weight,vector<int>& profit,int i){
if(i==weight.size()){     // if no item is left
return 0;
}
if(k==0){            // if knapsack is full
return 0;
}
int nPick = maxProfit(k,weight,profit,i+1);
int Pick = 0;
if(weight[i]<=k){
// we can pick this item if it's weight is less or
// equal to the current knapsack capacity
Pick = maxProfit(k-weight[i],weight,profit,i+1) + profit[i];
}
return max(nPick,Pick);
}
int main()
{
int n,k;
cin>>n>>k;
vector<int> weight(n), profit(n);
for(int i=0;i<n;i++){
cin>>weight[i]>>profit[i];
}
int i=0;
int result = maxProfit(k ,weight ,profit, i);
cout<<result<<"\n";
return 0;
}

Time complexity of this brute force recursive solution is exponential (2^n).

On observation, we can see that in the recursion tree of this algorithm, a sub-problem is computed multiple times.

Take an example:

n = 3, k=10

 i 1 2 3 Weight[i] 2 2 6 Profit[i] 8 5 9

maxProfit(k,i) represent a problem for knapsack with capacity k using i items.

Hence, we can use dynamic problem to solve this problem.

Approach:

1. Make a 2D matrix of n+1 rows and k+1 columns, where dp[i][j] will store the maximum profit we can get using i items for a knapsack of capacity j.
2. So to fill a cell dp[i][j] we have two options:
• Take the ith item: In this case your profit will be profit[i]+dp[i-1][j-weight[i]] .
• Don’t pick the ith item: In this case your profit will be same as profit that we get using i-1 items for knapsack capacity j i.e., dp[i-1][j].
3. The final ans would be maximum of these two options.

Implemented code in C++:

#include<bits/stdc++.h>
using namespace std;
int maxProfit(int k,vector<int>& weight,vector<int>& profit,int i){
int n=weight.size();
int dp[n+1][k+1];
// profit for knapsack with capacity 0 is always 0
for(int i=0;i<=n;i++){
dp[i]=0;
}

// profit will be 0 if we don't pick any item
for(int j=0;j<=k;j++){
dp[j]=0;
}

for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
// profit if we don't pick the ith item
dp[i][j]=dp[i-1][j];

//check if we can take the ith item or not
if(j>=weight[i-1]){
// final ans will be maximum from the two options
dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i-1]]+profit[i-1]);
}
}
}
return dp[n][k];
}
int main()
{
int n,k;
cin>>n>>k;
vector<int> weight(n), profit(n);
for(int i=0;i<n;i++){
cin>>weight[i]>>profit[i];
}
int i=0;
int result = maxProfit(k ,weight ,profit, i);
cout<<result<<"\n";
return 0;
}

Time Complexity of this algorithm is O(n*k) where n is the number of items and k is the capacity of knapsack.

Variant of Knapsack

What if we modify this question as:

Find the maximum profit that we can get to fill a knapsack of capacity k using n items given that there is unlimited supply of each item.

( This problem is known as Unbounded knapsack as there is no bound on the quantity of items )

The problem can be solved by doing just a minor change of:

dp[i][j]=max(dp[i][j],dp[i][j-weight[i-1]]

as after adding the ith item we can use that item again to get the profit for knapsack capacity of j-weight[i-1]

Implemented code in C++:

#include<bits/stdc++.h>
using namespace std;
int maxProfit(int k,vector<int>& weight,vector<int>& profit,int i){
int n=weight.size();
int dp[n+1][k+1];
// profit for knapsack with capacity 0 is always 0
for(int i=0;i<=n;i++){
dp[i]=0;
}

// profit will be 0 if we don't pick any item
for(int j=0;j<=k;j++){
dp[j]=0;
}

for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
// profit if we don't pick the ith item
dp[i][j]=dp[i-1][j];

//check if we can take the ith item or not
if(j>=weight[i-1]){
// final ans will be maximum from the two options
// for unbounded knapsack we will check the subproblem of dp[i][j-weight[i-1]]
// so that we can use that item again
dp[i][j]=max(dp[i][j],dp[i][j-weight[i-1]]+profit[i-1]);
}
}
}
return dp[n][k];
}
int main()
{
int n,k;
cin>>n>>k;
vector<int> weight(n), profit(n);
for(int i=0;i<n;i++){
cin>>weight[i]>>profit[i];
}
int i=0;
int result = maxProfit(k ,weight ,profit, i);
cout<<result<<"\n";
return 0;
}

That’s all I have and thanks a lot for reading 😉. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance…

Thanks Shiva Gupta for helping us to grow day by day. Shiva is expert in Data Structure and loves to solve competitive problems.

Categories: Dynamic Programming Divyansh Goel · April 7, 2020 at 4:47 pm

Explained beautifully with correct intuition

Insert math as
$${}$$