Dynamic Programming: Unbounded Knapsack Problem

Problem Statement:

You are given 2 arrays. Value array and corresponding weight associated with it.

You need to calculate the maximum amount that could make up for the total knapsack weight W.

The only difference from 0/1 knapsack problem is that, here the repetitions of the items are allowed.

Example

Input : W = 100
        val[]  = {1, 30}
        wt[]   = {1, 50}

Output : 100

1. You can either choose 2 units 50kg item. In this case the profit will be 60

2. Or you can take 100 units of 1kg item. In this case you will get the maximum profit 100.

Solution

First we will understand the question and then check how to change the 0/1 knapsack code to unbounded knapsack problem.

So this problem stats that we are allowed to take multiple instances of the same item.

So we have 2 choices:

Case 1: We choose the element. But according to the question we can choose the item multiple times.

Case 2: We do not choose the item.

So if you observe the case 1, that we can choose the item multiple time.
This is the only difference in 0/1 Knapsack with Unbounded Knapsack problem.

In the 0/1 knapsack, we had written the recurrence relation as:

max( profit+new weight if we choose the element,
     weight if we do not choose the element);

if(w[n-1] <= W)
    return max(val[n-1] + knapsack(weight, val, W-w[n-1], n-1),
               knapsack(weight, val, W, n-1));

If you observe this statement “val[n-1] + knapsack(weight, val, W-w[n-1], n-1”, we are actually reducing the array length by 1 if we choose the element.

But here we can choose that element multiple times. Hence there is no need to reduce the array length.

So the updated recurrence relation will be:

if(w[n-1] <= W)
    return max(val[n-1] + knapsack(weight, val, W-w[n-1], n),
               knapsack(weight, val, W, n-1));

rest of the code is same.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }

int knapsack_rec(int W, int wt[], int val[], int n)
{
  // base checks
  if (n == 0 || W == 0)
    return 0;


  if (wt[n - 1] > W)
    return knapsack_rec(W, wt, val, n - 1);
 
  else
        return max( val[n - 1] + knapsack_rec(W - wt[n - 1], wt, val, n ),
                    knapsack_rec(W, wt, val, n - 1));
}


int top_down_util(int W, int wt[], int val[], int i, vector<vector<int>> dp)
{
    if (i < 0)
        return 0;

    if (dp[i][W] != -1)
        return dp[i][W];
 
    if (wt[i] > W) {
        dp[i][W] = top_down_util(W, wt,
                               val, i - 1,
                               dp);
        return dp[i][W];
    }
    else {
        dp[i][W] = max(val[i]
                      + top_down_util(W - wt[i],
                                   wt, val,
                                   i, dp),
                       top_down_util(W, wt, val,
                                   i - 1, dp));
 
        return dp[i][W];
    }
}
 

int knapsack_top_down(int W, int wt[], int val[], int n)
{

    vector<vector<int>> dp(n+1, vector<int>(W + 1, -1));
    return top_down_util(W, wt, val, n - 1, dp);

}

int knapsack_bottom_up(int W, int wt[], int val[], int n)
{
    int i, w;
    int table[n + 1][W + 1];
 
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                table[i][w] = 0;
            else if (wt[i - 1] <= w)
                table[i][w] = max(val[i - 1]
                          + table[i][w - wt[i - 1]],
                          table[i - 1][w]);
            else
                table[i][w] = table[i - 1][w];
        }
    }
 
    return table[n][W];
}
 
int main()
{   
    int val[] = { 1, 30 };
    int wt[] = {  1, 50 };
    int W = 100;
    int n = sizeof(val) / sizeof(val[0]);
    cout << "The max profit using recursion is = "<<knapsack_rec(W, wt, val, n)<<endl;
    cout << "The max profit using top down is = "<<knapsack_top_down(W, wt, val, n)<<endl;
    cout << "The max profit using bottom up is = "<<knapsack_bottom_up(W, wt, val, n)<<endl;

  
}

Output:

The max profit using recursion is = 100
The max profit using top down is = 100
The max profit using bottom up is = 100