KnapSack DP 0/1


We are given a Knapsack (a Bag) with W weight capacity and a list of N items with given vi value and wi weight. Put these items in the knapsack in order to maximize the value of all the placed items without exceeding the limit of the Knapsack.

Thinking about the problem what we can think is that we can sort the items on the basis of values and take the items with maximum values without exceeding the weight capacity W.

Another thing that you can think of is sorting the items on the basis of weight and taking the minimum weight items as the bag will hold the maximum number of items.

But both of the above approaches will fail under different conditions.

 

Recursive Approach:

As the name suggests we will solve the problem using recursion. We have two choices to either take the current item or not take it. In this way, we will generate all the possible cases of either taking it or not taking it and then finding the answer.

Here is the code for this recursive approach.


#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

int helper(int idx,int n,vector<pii>&v){
    if(idx==0){
        if(v[0].first<=n)return v[0].second;
        return 0;
    }
    int notTake=0+helper(idx-1,n,v);
    int take=INT_MIN;
    if(v[idx].first<=n){
        take=v[idx].second+helper(idx-1,n-v[idx].first,v);
    }
    return max(take,notTake);
}


void solve() {

//n is the total number of items
//c is the maximum weight or cost

int  n,c;
cin>>n>>c;

//pii here is the pair<int,int>
vector<pii>v;
for (int i = 0; i < n; i++)
{
    int x,y;
    cin>>x>>y;
    v.push_back({x,y});
}

cout<<helper(n-1,c,v);
}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
//   cin >> t; 
  while (t--) solve();



  return 0;
}


The above code will lead us to Time Limit Exceeded so we need to optimize the code. We can see that we are calling the helper function again and again for the same arguments. What we can do is we can store the value of the function in a data structure and we can use the data whenever needed.

We will make a vector of vectors and name it dp.

See the code below for a better understanding.

#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

int helper(int idx,int n,vector<pii>&v,vector<vector<int>>&dp){
    if(idx==0){
        if(v[0].first<=n)return v[0].second;
        return 0;
    }
    if(dp[idx][n]!=-1)return dp[idx][n];
    int notTake=0+helper(idx-1,n,v,dp);
    int take=INT_MIN;
    if(v[idx].first<=n){
        take=v[idx].second+helper(idx-1,n-v[idx].first,v,dp);
    }
    return dp[idx][n]=max(take,notTake);
}


void solve() {
// n is the number of items and c is the maximum capacity

int  n,c;
cin>>n>>c;
//pii is pair<int,int>
vector<pii>v;
for (int i = 0; i < n; i++)
{
    int x,y;
    cin>>x>>y;
    v.push_back({x,y});
}
vector<vector<int>>dp(n,vector<int>(c+1,-1));
cout<<helper(n-1,c,v,dp);
}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
//   cin >> t; 
  while (t--) solve();



  return 0;

} 


Tabulation

1. Write Base Case

2. See what is changing, here items and their weight is changing

3. Use Recurrence

 

Finding Base Case:

We will see the first items if its weight is greater than max capacity then we will leave it zero or else from its weight to max weight we will change the value to its value.

See What is changing:

Here we are changing the item number and starting the capacity from 0 to max.

 

See the Below code for implementation.

 


#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

int helper(int idx,int n,vector<pii>&v,vector<vector<int>>&dp){
    if(idx==0){
        if(v[0].first<=n)return v[0].second;
        return 0;
    }
    if(dp[idx][n]!=-1)return dp[idx][n];
    int notTake=0+helper(idx-1,n,v,dp);
    int take=INT_MIN;
    if(v[idx].first<=n){
        take=v[idx].second+helper(idx-1,n-v[idx].first,v,dp);
    }
    return dp[idx][n]=max(take,notTake);
}


void solve() {


int  n,c;
cin>>n>>c;

vector<pii>v;
for (int i = 0; i < n; i++)
{
    int x,y;
    cin>>x>>y;
    v.push_back({x,y});
}
vector<vector<int>>dp(n,vector<int>(c+1,0));
// cout<<helper(n-1,c,v,dp);

for (int i = v[0].first; i <= c; i++)
{
    dp[0][i]=v[0].second;
}

for (int i = 1; i < n; i++)
{
    for (int j = 0; j <=c ; j++)
    {
        int notTake=dp[i-1][j];
        int take=INT_MIN;
        if(v[i].first<=j){
        take=v[i].second+dp[i-1][j-v[i].first];
        }
        dp[i][j]=max(notTake,take);
    }
    
}
cout<<dp[n-1][c];

}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
//   cin >> t; 
  while (t--) solve();



  return 0;
}


We will now optimize it for space. Instead of making vector<vector<int>> we will just use two vectors. As we can see is that at max we are using the previous row of the matrix we can store it in prev.

See the Code for a better understanding.


#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

int helper(int idx,int n,vector<pii>&v,vector<vector<int>>&dp){
    if(idx==0){
        if(v[0].first<=n)return v[0].second;
        return 0;
    }
    if(dp[idx][n]!=-1)return dp[idx][n];
    int notTake=0+helper(idx-1,n,v,dp);
    int take=INT_MIN;
    if(v[idx].first<=n){
        take=v[idx].second+helper(idx-1,n-v[idx].first,v,dp);
    }
    return dp[idx][n]=max(take,notTake);
}


void solve() {
int  n,c;
cin>>n>>c;

vector<pii>v;
for (int i = 0; i < n; i++)
{
    int x,y;
    cin>>x>>y;
    v.push_back({x,y});
}
vector<int>prev(c+1,0);
// cout<<helper(n-1,c,v,dp);

for (int i = v[0].first; i <= c; i++)
{
    prev[i]=v[0].second;
}

for (int i = 1; i < n; i++)
{
    vector<int>curr(c+1,0);
    for (int j = 0; j <=c ; j++)
    {
        int notTake=prev[j];
        int take=INT_MIN;
        if(v[i].first<=j){
        take=v[i].second+prev[j-v[i].first];
        }
        curr[j]=max(notTake,take);
    }
    prev=curr;
    
}
cout<<prev[c];
}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
//   cin >> t; 
  while (t--) solve();



  return 0;
}

 sdfsdf