Unbounded Knapsack Problem

#cpp #algorithms #programming

The unbounded knapsack problem is a dynamic programming-based problem and also an extension of the classic 0-1 knapsack problem. You can read about 0-1 knapsack problem here.

Problem Description

Given n weights having a certain value put these weights in a knapsack with a given capacity (maxWeight). The total weight of the knapsack after adding weights must remain smaller than or equal to capacity(maxWeight). The goal here is to find possible maximum total value in the knapsack. Any weight can be selected multiple times i.e. repetitions are allowed. For example :

Input:
n=2
maxWeight=3
weights={2,1}
value={1,1}

Output:
3

In the above example, we can select weights {1} for 3 times giving knapsack total weight as 3 and total value as 3 which is the maximum possible value.

Observation

Here the key observation is that we need to find the subset of weights whose weight sum is less than or equal to the capacity of the knapsack and having maximum value sum. Here any weight can be added multiple times in the subset.

Recursive Approach

Recursively we will move from index 0 to n-1 and will perform two operations:

Add the current weight. We will only select the current weight if the total weight inside the knapsack after selecting remains under the given capacity else will ignore it. If selected, we will call for the same index again because we can select a weight more than once.
Don't add the current weight. Here we will move to the next index (i.e i+1)

We will return the maximum of both operations as we have to maximize the total value. Here we will stop at index==n because there's no weight to add in the knapsack. You can see in the code that it is selecting the weight and calling the same index again to check if the same weight can be added again. Also, we are considering the possibility of not selecting the weight. So in the end, the maximum answer for a particular weight after considering both possibilities is returned. At last, we have final answer.

        int rec_helper(int curWeightSum,int i,int n,int wt[],int val[],int maxWeight,int **dp){
            if(i==n){
                return 0;
            }
            if(dp[i][curWeightSum]!=-1){
                return dp[i][curWeightSum];
            }
            dp[i][curWeightSum] = rec_helper(curWeightSum,i+1,n,wt,val,maxWeight,dp);
            if(curWeightSum+wt[i]<=maxWeight) {
                dp[i][curWeightSum] = max(dp[i][curWeightSum],
                                          val[i] + rec_helper(curWeightSum + wt[i], i, n, wt, val, maxWeight, dp));
            }
            return dp[i][curWeightSum];
        }
        int unbounded_knapsack(int n,int wt[],int val[],int maxWeight){
            int** dp=new int*[n];
            for(int i=0;i<n;i++){
                dp[i]=new int[maxWeight+1];
                for(int j=0;j<maxWeight+1;j++){
                    dp[i][j]=-1;
                }
            }
            return rec_helper(0,0,n,wt,val,maxWeight,dp);
        }

Memoization - Here I used a 2d array - 'dp' to store the recursion calls so that we can use the stored value in dp for repeated recursion calls instead. This is useful for reducing time complexity.

Time Complexity : O(n*maxWeight*maxWeight). For every weight we are going till maxWeight. And every weight is selected for multiple times reaching maxweight.
Space Complexity : O(n*maxWeight). We used 2-d array dp as extra space

Dynamic Approach

Tabulation is done using a one-dimensional array(dp) in this case. Whose dimension is the same as maxWeight+1. Here we do the same two operations stated in the recursive approach:

If we have to form a knapsack of capacity j and we have current weight under consideration as weights[i], which is <=j, with value[i]. If we add the current weights[i] in the knapsack, we need to find the maximum value for the knapsack of total weight (j-weight[i]) from the dp which contains solutions till current weight(included), and then add value[i] of weights[i] weight in that. In case we don't have a knapsack of total weight (j-weights[i]) then 0 will be added and the value[i] of current weights[i] will become the total of values for that particular knapsack. If we have the current weight as 3 and required j=5 then we need to find a knapsack of weight 5-3=2. Here the important difference from 0-1 knapsack problem is that we are iterating the dp from 0 to maxWeight(included). This is because we also need solutions for current weight till the current required knapsack weight(j) as weights can be used for multiple times.
If we don't select the weight, the value of that cell remains unchanged as it already describes the answer till now for particular j.

         int unbounded_knapsack(int n,int wt[],int val[],int maxWeight){
            int dp[maxWeight+1];
            for(int i=0;i<maxWeight+1;i++){
                dp[i]=0;
            }
            for(int i=0;i<n;i++){
                for(int j=wt[i];j<maxWeight+1;j++){
                    dp[j]=max(dp[j],val[i]+dp[j-wt[i]]);
                }
            }
            return dp[maxWeight];
        }

Here the cell value in the dp array will be the maximum of operation1 and operation2. I used 1-d array, where jth cell represents a knapsack with weight j while performing operations on a particular ith weight. Hence the array will hold results till (i-1)th weight while running for ith weight. Returning dp[maxWeight] will give the answer. Initially, all the values of the array is 0 as it will be the maximum for an empty knapsack.

Time Complexity : O(n*maxWeight).
Space Complexity : O(maxWeight). We used 2-d array dp as extra space