Solving Unbounded Knapsack Problem using Dynamic Programming

Reading time: 30 minutes | Coding time: 10 minutes

Knapsack problem refers to the problem of optimally filling a bag of a given capacity with objects which have individual size and benefit. The objective is the increase the benefit while respecting the bag's capacity.

In the original problem, the number of items are limited and once it is used, it cannot be reused. This restriction is removed in the new version: Unbounded Knapsack Problem. In this case, an item can be used infinite times. This problem can be solved efficiently using Dynamic Programming.

Problem Statement

Given N items each with an associated weight and value (benefit or profit). The objective is to fill the knapsack with items such that we have a maximum profit without crossing the weight limit of the knapsack. In the Unbounded version of the problem, we are allowed to select one item multiple times, unlike the classical one, where one item is allowed to be selected only once.

Example:

Suppose we have three items which is defined by a tuple (weight, benefit). The items are:

(7, 12) ; (3, 2), (20, 41)

We have a bag with capacity 58. In this case, the optimal filling will be:

Item 3 + 3 + 1 + 1 + 2

Note the total benefit is (41+41+12+12+2) = 108 with total weight being 57 (< 59).

We could have covered all the weight like:

Item 3 + 3 + 2 + 2 + 2 + 2 + 2 + 2

The total weight will become 59 but the benefit will be (41 * 2 + 2 * 6) = 94 (< 108)

Hence, in the previous combination, we have taken the optimal distribution.

Brute Force Approach

If we are given a set of items with their weights and profits and we are asked to compute the maximum possible profit of them, the first approach we'd think of would be the brute-force one. Here, we'll try all possible combinations of items and would take note of profits we achieve in each of them and finally, compute the maximum of those profits as our answer.

Pseudocode :

maxProfit = 0
for i = 0 to 2^N:
    bin = binary(i)                 // Convert the number to binary
    profit = 0
    weight = 0
    for j = 0 to bin.length():
        if bin[j] is set:           // If the bit j is set, we have to include that item.
            if weight + wt[j] > W:  // When weight of the combination exceeds Capacity, Break.
                profit = 0
                break
            profit = profit + val[j]
            weight = weight + wt[j]
     maxProfit = max(maxProfit, profit)  // Update max profit.      

This way, choosing from all combination would mean a time complexity of order

Θ(2^N)

as there are total nC0 + nC1 + .. nCn = 2^n possible combinations of n items. This would be highly inefficient, given the computation time. Thus, we use dynamic programming method.

Dynamic Programming Approach

We use dynamic programming approach to solve this problem, similar to what we did in classical knapsack problem. The only difference is we would use a single dimensional array instead of 2-D one used in the classical one. This is because we have infinite supply of every element available to us and hence, we don't need to keep a track of which elements have been used.

Thus, our array would be dp[W+1] , where dp[i] indicates the maximum profit we can achieve with a knapsack capacity of i. Here, W is the total knapsack capacity, hence our answer would be dp[W].

dp[i] = maximum profit we can achieve with a knapsack capacity of i

Programmatically, we iterate over all the elements available for each knapsack capacity between 1 to W and determine if it can be used to achieve a greater profit.

Thus, our dp equation would look something like-

dp[i] = max(dp[i], dp[i-wt[j]] + val[j]) if wt[j] < i (item j is taken)

Pseudocode:

    for i = 0 to W:
        for j = 0 to N:
            if wt[j] < i :
                dp[i] = max(dp[i], dp[i-wt[j]] + val[j])

Suppose we are given 4 items, with weight 1,2,5 and 3 respectively and the profits associated with them are 40,30,50 and 25 in the same order. The capacity of the knapsack is given as 2.

Proceeding with our approach, initially, our dp array is set to 0. We begin iterating from 1 to 6 (capacity of knapsack).

Our wt array = [1,2,5,3]
Our val array = [40,30,50,20]
Initial dp array = [0,0,0]

First Iteration (i=0)

j=0 : wt[j] <= i not satisfied. (wt[0] = 1, i = 0)
j=1 : wt[j] <= i not satisfied. (wt[1] = 2, i = 0)
j=2 : wt[j] <= i not satisfied. (wt[2] = 5, i = 0)
j=3 : wt[j] <= i not satisfied. (wt[3] = 3, i = 0) </br>
dp array after First iteration = [0,0,0]

Second Iteration (i=1)

j=0 : wt[j] <= i is satisfied. (wt[0] = 1, i = 1)  
Thus, dp[1] = max(dp[1],dp[1-1]+val[0]) = max(0,0+40)=40.

j=1 : wt[j] <= i not satisfied. (wt[1] = 2, i = 1)
j=2 : wt[j] <= i not satisfied. (wt[2] = 5, i = 1)
j=3 : wt[j] <= i not satisfied. (wt[3] = 3, i = 1)
dp array after Second iteration = [0,40,0]

Third Iteration (i=2)

j=0 : wt[j] <= i is satisfied. (wt[0] = 1, i = 2) 
Thus, dp[2] = max(dp[2],dp[2-1]+val[0]) = max(0,40+40)=80.

j=1 : wt[j] <= i is satisfied. (wt[1] = 2, i = 2) 
Thus, dp[2] = max(dp[2],dp[2-2]+val[1]) = max(80,0+30)=80.

j=2 : wt[j] <= i not satisfied. (wt[2] = 5, i = 2)
j=3 : wt[j] <= i not satisfied. (wt[3] = 3, i = 2)
Final dp array = [0,40,80]

Now, since i = W (knapsack capacity), our iteration would stop. So, the maximum profit that we can achieve is dp[2] = 80. By using item 1 two times, as it has weight = 1 and profit = 40.

Complexities

• Time complexity: Θ((W+1)*N). As we can take all items multiple number of times, we check all of them(1 to N) for all weights from 0 to W. Hence, time complexity = (W+1) * N.
• Space complexity: Θ(W+1). We maintain a dp array of size W+1, where dp[i] denotes the maximum profit for capacity i. Hence, space complexity = W+1

Here, W = Knapsack Capacity, N = No. of items.

Implementations

We provide the Dynamic Programming implementation in three languages C++, Python and Java.

Implementation in C++:

    #include <bits/stdc++.h>
    using namespace std;
    long int UnboundedKnapsack(long int Capacity,long int n, long int weight[],long int val[]){
        long int dp[Capacity+1];
        for(int i=0;i < W+1;i++){
            dp[i]=0;                            
        }
        for(int i=0;i < W+1;i++){
            for(int j=0;j < n;j++){
                if(weight[j] < i){
                    dp[i] = max(dp[i], dp[i-weight[j]] + val[j]);   
                }
            }
        }
        return dp[Capacity];
    }
    int main(){
        //  The no. of items : 
        long int n = 4;
        //  Weights of all the items : 
        long int weight[4] = {5 , 10, 8, 15};
        //  Enter values of all the items : 
        long int val[4] = {40, 30, 50, 25};
        // Enter the knapsack capacity : 
        long int Capacity = 120;
        cout << "The maximum value you can achieve in Unbounded Knapsack is: " << UnboundedKnapsack(W,n,wt,val);
        return 0;
    }

Implementation in Python:

# Unbounded Knapsack Problem
def UnboundedKnapsack(Capacity,n,weight,val):
    dp=[]
    for i in range(Capacity+1):
        dp.append(0)
    for i in range(0,Capacity+1):
        for j in range(0,n):
            if weight[j] < i:
                dp[i] = max(dp[i] , dp[i-weight[j]]+val[j])
    return dp[Capacity]
''' No. of items '''
n = 4
''' Weights of all items '''
weight = [5,10,8,15]
''' Values of all items '''
val = [40,30,50,25]
''' Capacity of Knapsack '''
Capacity = 120
print("The maximum value possible is ",UnboundedKnapsack(Capacity,n,weight,val))

Implementation in Java:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
    public static int unboundedKnapsack(int Capacity,int n, int weight[],int val[]){
        int[] dp = new int[Capacity+1];
        for(int i=0;i < Capacity;i++){
            dp[i]=0;
        }
        for(int i=0;i < Capacity;i++){
            for(int j=0;j < n;j++){
                if(weight[j] < i){
                    dp[i]=Math.max(dp[i],dp[i-weight[j]]+val[j]);
                }
            }
        }
        return dp[Capacity];
    }
    public static void main(String[] args) {
       // No. of items
       int n = 4;
       // Values(Profits) of items
       int val[] = {40,30,50,25};
       // Weight of items
       int weight[] = {5,10,8,15};
       // Knapsack capacity
       int Capacity = 120;
       System.out.println("Maximum value that can be achieved is: "+unboundedKnapsack(Capacity,n,weight,val));
   }
}

Question