Skip to content

Unbounded 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 multiple times
    • we should not take the item
    • you cannot take half of the item

recursive sol

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

// state represented by (W, n)
int knapSack(vector<int>wt, vector<int>val, int W, int n){
    // base case, items are over or knapsack is full
    if (n == 0 || W == 0) return 0;
    // can we add current item
    if (wt[n - 1] <= W)
        return max(
            val[n - 1] + knapSack(wt, val, W - wt[n - 1], n), // use item and remain on same item
            knapSack(wt, val, W, n - 1) // mode to next item
        );
    else
        return knapSack(wt, val, W, n - 1); // move to next item
}

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 for storing result of the cache -> (W, n)
vector<vector<int>> dp;

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

    // get result form the cache
    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),
            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){

    // storing results for the state (W, n)
    // state results array
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

    // basecases are already initialized to 0

    // iterating over rest of the states

    // going through items
    for(int i=1;i<n+1;i++){
        // going through weight
        for(int j=1;j<W+1;j++){
            if(wt[i-1] <= j)
                dp[i][j] = max(
                        val[i-1] + dp[i][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