Problem Statement:
Given a knapsack of capacity W and a set of n items with certain value val[i] and weight wt[i], we need to calculate the maximum value that we can generate from the given weights of n items such that it does not exceed the given capacity W and the value is maximum.
This is different from the classical 0-1 Knapsack problem, here we are allowed to use an unlimited number of instances of an item.
Input:
n : 5
W : 8
wt : [1, 3, 4, 5, 9]
val : [10, 40, 50, 70, 60]
Output:
110
Explanation:
The key difference between 0-1 Knapsack and Unbounded Knapsack is the one that, In 0-1 Knapsack, if we have included one item in our answer we cannot include the same item again whereas in Unbounded Knapsack the word unbounded itself tells us that we can include the same item again and again. That means we have an unlimited supply of each item.
To understand it in a more clear way let’s look at the below image.
In the above diagram, the weight of the last element is 9 but we have a capacity of 8 only. Hence, we cannot include this element in our answer. Therefore, we will simply reduce our search area. Now, let’s look at the next step.
In the above diagram, we are having now 4 elements in our search area. Therefore, we will look at the next element which is 5. Here, the weight 5 is smaller than our capacity which is 8. Therefore, we have two choices.
- Either including this can give me the best answer
- Or, excluding this can give me the best answer
Hence, we will take both possibilities. Because both possibilities can give me different answers. Hence, we will take the maximum of these two.
The point to be noted here is that when we included element 5 in our answer, we will not reduce our search area, and hence we can include this item again in our answer.
Suppose we have a function unboundedKnapsack(wt, val, W, n) which calculates our answer. Therefore, what our recursive calls will look like?
if (wt[n - 1] > W) {
return unboundedKnapsack(wt, val, W, n - 1);
}
If the weight is greater than the capacity, we are direct excluding the element and calling our recursive function for the reduced size of the array.
otherwise return max(unboundedKnapsack(wt, val, W, n - 1), val[n - 1] + unboundedKnapsack(wt, val, W - wt[n - 1], n));
Otherwise, if the weight is smaller or equal to the capacity, then we have to take the max of inclusion and exclusion.
What will be the base case?
Case 1: Suppose, if we don’t have any number of items and we have W capacity. Can we buy any item? Of course NO.
Case 2: Suppose, if we have n items but we have no capacity. Can we buy any items? Of course NO.
That means when we can’t buy any item, then we can’t make any profit. Hence in these two cases when our n becomes 0 or W becomes 0. We will return 0.
if(W == 0 || n == 0) {
return 0;
}
Let’s jump onto the code:
Java Code:
import java.io.*;
class Innoskrit {
public static int unboundedKnapsack(int wt[], int val[], int W, int n) {
if (W == 0 || n == 0)
return 0;
if(wt[n - 1] > W)
return unboundedKnapsack(wt, val, W, n - 1);
return Math.max(unboundedKnapsack(wt, val, W, n - 1), val[n - 1] + unboundedKnapsack(wt, val, W - wt[n - 1], n));
}
public static void main (String[] args) {
int n = 5;
int W = 8;
int wt[] = {1, 3, 4, 5, 9};
int val[] = {10, 40, 50, 70, 60};
int value = unboundedKnapsack(wt, val, W, n);
System.out.println(value);
}
}
C++ Code:
#include <iostream>
#include <vector>
using namespace std;
class Innoskrit {
public:
static int unboundedKnapsack(const vector<int>& wt, const vector<int>& val, int W, int n) {
if (W == 0 || n == 0)
return 0;
if(wt[n - 1] > W)
return unboundedKnapsack(wt, val, W, n - 1);
return max(unboundedKnapsack(wt, val, W, n - 1), val[n - 1] + unboundedKnapsack(wt, val, W - wt[n - 1], n));
}
};
int main(int argc, char * argv[]) {
int n = 5;
int W = 8;
vector<int> wt = {1, 3, 4, 5, 9};
vector<int> val = {10, 40, 50, 70, 60};
int value = Innoskrit::unboundedKnapsack(wt, val, W, n);
cout << value << endl;
}
Python Code:
def unboundedKnapsack(wt, val, W, n):
if W == 0 or n == 0:
return 0
if wt[n - 1] > W:
return unboundedKnapsack(wt, val, W, n - 1)
return max(unboundedKnapsack(wt, val, W, n - 1), val[n - 1] + unboundedKnapsack(wt, val, W - wt[n - 1], n))
if __name__ == '__main__':
n = 5
W = 8
wt = [1, 3, 4, 5, 9]
val = [10, 40, 50, 70, 60]
ans = unboundedKnapsack(wt, val, W, n)
print(ans)
Time Complexity: O(2 ^ N)
In every recursive call, we are making a maximum of 2 calls to the same function. Hence, the time complexity will be O(2^N)
Space Complexity: O(N) for storing activation records of the recursive calls.
Can we improve this? Of course YES! We’ll use Dynamic Programming.
Let’s look at why do we need Dynamic Programming here to solve this problem.
Top-Down Dynamic Programming with Memoization
In the above diagram, if you see carefully we have some recursive calls repeating that we have already computed. Therefore, we should save these recursive calls somewhere for given W and n. Hence, we can use the Memoization (Top-Down) technique to efficiently solve overlapping sub-problems. To do so, we will create a table of size (n + 1) x (W + 1) to save the values for already computed calls.
Let’s look at the code.
Java Code:
import java.io.*;
class Innoskrit {
public static int unboundedKnapsack(int wt[], int val[], int W, int n, int dp[][]) {
if(W == 0 || n == 0)
dp[n][W] = 0;
if(dp[n][W] != -1)
return dp[n][W];
if(wt[n - 1] > W)
return dp[n][W] = unboundedKnapsack(wt, val, W, n - 1, dp);
else
return dp[n][W] = Math.max(unboundedKnapsack(wt, val, W, n - 1, dp), val[n - 1] + unboundedKnapsack(wt, val, W - wt[n - 1], n, dp));
}
public static void main (String[] args) {
int n = 5;
int W = 8;
int wt[] = {1, 3, 4, 5, 9};
int val[] = {10, 40, 50, 70, 60};
int dp[][] = new int[n + 1][W + 1];
for(int i = 0; i < n + 1; i++)
for(int j = 0; j < W + 1; j++)
dp[i][j] = -1;
int value = unboundedKnapsack(wt, val, W, n, dp);
System.out.println(value);
}
}
CPP Code:
#include <iostream>
#include <vector>
using namespace std;
class Innoskrit {
public:
static int unboundedKnapsack(const vector<int>& wt, const vector<int>& val, int W, int n, vector<vector<int>>& dp) {
if(W == 0 || n == 0)
dp[n][W] = 0;
if(dp[n][W] != -1)
return dp[n][W];
if(wt[n - 1] > W)
return dp[n][W] = unboundedKnapsack(wt, val, W, n - 1, dp);
else
return dp[n][W] = max(unboundedKnapsack(wt, val, W, n - 1, dp), val[n - 1] + unboundedKnapsack(wt, val, W - wt[n - 1], n, dp));
}
};
int main(int argc, char * argv[]) {
int n = 5;
int W = 8;
vector<int> wt = {1, 3, 4, 5, 9};
vector<int> val = {10, 40, 50, 70, 60};
vector<vector<int>> dp(n + 1, vector<int> (W + 1, -1));
int value = Innoskrit::unboundedKnapsack(wt, val, W, n, dp);
cout << value << endl;
}
Python Code:
def unboundedKnapsack(wt, val, W, n, dp):
if W == 0 or n == 0:
dp[n][W] = 0
# if you have already computed the answer for n & W, return it from the table
if dp[n][W] != -1:
return dp[n][W]
if wt[n - 1] > W:
dp[n][W] = unboundedKnapsack(wt, val, W, n - 1, dp)
return dp[n][W]
dp[n][W] = max(unboundedKnapsack(wt, val, W, n - 1, dp), val[n - 1] + unboundedKnapsack(wt, val, W - wt[n - 1], n, dp))
return dp[n][W]
if __name__ == '__main__':
n = 5
W = 8
wt = [1, 3, 4, 5, 9]
val = [10, 40, 50, 70, 60]
dp = [[-1] * (W + 1) for i in range(n + 1)]
ans = unboundedKnapsack(wt, val, W, n, dp)
print(ans)
Since our memoization array dp[n + 1][W + 1] stores the results for all subproblems, we can conclude that the time complexity will be O(n * W).
The above algorithm will use O(n * W) space for the memoization array. Other than that we will use O(n) space for the recursion call stack. So the total space complexity will be O(n * W + n), which is asymptotically equivalent to O(n * W)
Bottom-up Dynamic Programming
Let’s try to populate our dp[][] array from the above solution by working in a bottom-up fashion. Essentially, we want to find the maximum profit for every sub-list of items and for every possible capacity W. This means that dp[i][j] will represent the maximum knapsack profit for capacity ‘j’ calculated from the first ‘i’ items.
So, for each item at index ‘i’ (0 <= i <= n) and capacity ‘j’ (0 <= j <= W), we have two options:
- Exclude the item at index ‘i’. In this case, we will take whatever profit without including this item i.e
dp[i-1][j]. - Include the item at index ‘i’ if its weight is not more than the capacity. In this case, we include its value plus whatever value we get from the remaining capacity and from remaining items i.e
val[i - 1] + dp[i-1][j - wt[i - 1]] - Finally, our optimal solution will be the maximum of the above two values:
dp[i][j] = max(dp[i-1][j], val[i - 1] + dp[i - 1][j - wt[i - 1]])
Intuition:
- In this
dp[][]array, the 0th column tells us, the capacity as 0 and the 0th row tells us the number of items as 0. Hence our base case will be represented as shown below:
- Now when we will iterate over this table. Each of the
jvalues will tell us the capacity and each of theivalue will tell us the number of items that we are considering. - For example:
i = 1andj = 1means that we have capacity as 1 and number of items as 1. Means,wt[i - 1] <= j. Therefore, we have two choices: either we can include this in our answer or we can exclude this. - Similary, let’s suppose
i = 2andj = 1which means that we still have a capacity of 1 but we are cosidering 2 items. In this casewt[i - 1]> j and this is the case when we have to directly exclude the item becasewt[i - 1] = 3andj = 1. Hence we cannot put weight 3 in a knapsack having capacity of 1.
Let’s look at the whole table after we execute the above scenarios for all possible values of i and j.
Let’s look at the code for bottom-up DP.
Java Code:
import java.io.*;
class Innoskrit {
public static int unboundedKnapsack(int wt[], int val[], int W, int n) {
int dp[][] = new int[n + 1][W + 1];
for(int i = 0; i < n + 1; i++)
for(int j = 0; j < W + 1; j++)
dp[i][j] = 0;
for(int i = 1; i < n + 1; i++) {
for(int j = 1; j < W + 1; j++) {
if(wt[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(dp[i - 1][j], val[i - 1] + dp[i][j - wt[i - 1]]);
}
}
return dp[n][W];
}
public static void main (String[] args) {
int n = 5;
int W = 8;
int wt[] = {1, 3, 4, 5, 9};
int val[] = {10, 40, 50, 70, 60};
int dp[][] = new int[n + 1][W + 1];
int value = unboundedKnapsack(wt, val, W, n);
System.out.println(value);
}
}
C++ Code:
#include <iostream>
#include <vector>
using namespace std;
class Innoskrit {
public:
static int unboundedKnapsack(const vector<int>& wt, const vector<int>& val, int W, int n) {
vector<vector<int>> dp(n + 1, vector<int> (W + 1, 0));
for(int i = 1; i < n + 1; i++) {
for(int j = 1; j < W + 1; j++) {
if(wt[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], val[i - 1] + dp[i][j - wt[i - 1]]);
}
}
return dp[n][W];
}
};
int main(int argc, char * argv[]) {
int n = 5;
int W = 8;
vector<int> wt = {1, 3, 4, 5, 9};
vector<int> val = {10, 40, 50, 70, 60};
int value = Innoskrit::unboundedKnapsack(wt, val, W, n);
cout << value << endl;
}
Python Code:
def unboundedKnapsack(wt, val, W, n):
dp = [[0] * (W + 1) for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, W + 1):
if wt[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], val[i - 1] + dp[i][j - wt[i - 1]])
return dp[n][W]
if __name__ == '__main__':
n = 5
W = 8
wt = [1, 3, 4, 5, 9]
val = [10, 40, 50, 70, 60]
ans = unboundedKnapsack(wt, val, W, n)
print(ans)
Time and Space Complexity:
Since our array dp[n + 1][W + 1] stores the results for all subproblems, we can conclude that the time complexity will be O(n * W).
The above algorithm will use O(n * W) space for the dp array.