Skip to content

0/1 knapsack type problem

Description

  • we are given
    • two arrays - one for the weight of item and one for the price
    • a value which is equal to the capacity of knapsack
  • for each item we have a choice
    • we should take the item
    • we should not take the item
    • you cannot take half of the item

Recursive Solution

#include<bits/stdc++.h>
using namespace std;

// only things that change represent state
// here state is -> (W, n)
int knapSack(
    vector<int>wt, // weight of items array
    vector<int>val, // value associated with each item
    int W, // amount of weight we can add to knapsack
    int n // current item + 1 number
){
    // base condition, when either knapsack is full, or items are over
    if (n == 0 || W == 0) return 0;

    // if current item can be stored in the knapsack
    if (wt[n - 1] <= W) {
        return max(
            val[n - 1] + knapSack( wt, val, W - wt[n - 1], n - 1),
            knapSack(wt, val, W, n - 1)
        );
    }
    else {
        return knapSack(wt, val, W, n - 1);
    }
}

int main(){
    vector<int> val = { 60, 100, 120 };
    vector<int> wt = { 10, 20, 30 };
    int n = val.size();
    int W = 50;
    cout << knapSack(wt, val, W, val.size());
    return 0;
}

Memoization solution

#include<bits/stdc++.h>
using namespace std;

// cache the state results, state is represented by (W, n), values that change
vector<vector<int>> dp;

int knapSack(vector<int>wt, vector<int>val, int W, int n){
    // base case
    if (n == 0 || W == 0) return 0;

    // getting cache result
    if(dp[n][W] != -1) return dp[n][W];

    if (wt[n - 1] <= W)
        return dp[n][W] = max(
            val[n - 1] + knapSack(wt, val, W - wt[n - 1], n - 1),
            knapSack(wt, val, W, n - 1)
        );
    else
        return dp[n][W] = knapSack(wt, val, W, n - 1);
}

int main(){
    vector<int> val = { 60, 100, 120 };
    vector<int> wt = { 10, 20, 30 };
    int n = val.size();
    int W = 50;
    dp = vector<vector<int>> (n+1, vector<int>(W+1, -1));
    cout << knapSack(wt, val, W, n);
    return 0;
}

top down approach

#include<bits/stdc++.h>
using namespace std;

int knapSack(int W, vector<int>wt, vector<int>val, int n){
    // state cache, (n, W) represented state
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

    // for base case solution is already 0, which is as initialized

    // finding solution for remaining problems

    // for iterating through the item state set
    for(int i=1;i<n+1;i++){
        // for iterating though the weight state sets
        for(int j=1;j<W+1;j++){
            if(wt[i-1] <= j)
                dp[i][j] = max(val[i-1] + dp[i-1][j-wt[i-1]], dp[i-1][j])
            else
                dp[i][j] = dp[i-1][j];
        }
    }

    return dp[n][W];
}

int main(){
    vector<int> val = { 60, 100, 120 };
    vector<int> wt = { 10, 20, 30 };
    int n = val.size();
    int W = 50;
    cout << knapSack(W, wt, val, n);
    return 0;
}

practice que