Unbounded Knapsack Problem(Repetition of items allowed)
Description
You are given a knapsack that can hold a maximum weight called capacity, along with n items. Each item has an associated weight stored in the array wt[] and a corresponding profit stored in the array val[].
Your goal is to fill the knapsack to achieve the maximum total profit. The key twist in this variant is that each item can be picked an unlimited number of times — you are not restricted to using an item only once. You may place multiple copies of the same item into the knapsack as long as the total weight does not exceed the given capacity.
Return a single integer representing the maximum profit achievable.
Examples
Example 1
Input: val = [15, 25], wt = [2, 3], capacity = 5
Output: 40
Explanation: We pick item 0 (weight 2, value 15) once and item 1 (weight 3, value 25) once. Total weight = 2 + 3 = 5, which exactly fills the knapsack. Total profit = 15 + 25 = 40. Alternatively, picking item 0 twice (weight 4, value 30) leaves capacity 1 unused, giving only 30. Taking item 1 once with remaining capacity 2 allows one more item 0 for the best total of 40.
Example 2
Input: val = [10, 40, 50, 70], wt = [1, 3, 4, 5], capacity = 8
Output: 110
Explanation: Pick item 1 (weight 3, value 40) and item 3 (weight 5, value 70). Total weight = 3 + 5 = 8, total profit = 40 + 70 = 110. Other combinations like eight copies of item 0 (profit 80) or two copies of item 2 (profit 100) yield less.
Example 3
Input: val = [5, 10, 15], wt = [3, 4, 5], capacity = 2
Output: 0
Explanation: Every item weighs at least 3, but the knapsack can only hold weight 2. No item fits, so the maximum profit is 0. This is an important edge case — when all items are heavier than the knapsack capacity, the answer is always 0.
Constraints
- 1 ≤ val.size() = wt.size() ≤ 1000
- 1 ≤ capacity ≤ 1000
- 1 ≤ val[i], wt[i] ≤ 100
Editorial
Brute Force
Intuition
Imagine you are standing in front of a store shelf with items, each having a price tag (weight) and a reward (value). You have a bag that can carry up to a certain total weight. You want to maximize the total reward. The simplest strategy is to try every possible combination of items.
For each item, you have two choices:
- Take it — add its value to your profit, reduce the remaining capacity by its weight, and consider the same item again (since repetition is allowed).
- Skip it — move on to the next item without taking it.
This naturally forms a recursive decision tree. At every node, you branch into "take" and "skip," exploring all possibilities and returning the maximum profit found across all branches.
The critical difference from the standard 0/1 knapsack is in the "take" branch: after taking an item, you do not move to the next item. You stay at the same item index because you are allowed to pick it again. You only advance to the next item when you explicitly choose to "skip."
Step-by-Step Explanation
Let's trace through with val = [15, 25], wt = [2, 3], capacity = 5:
Step 1: Start at solve(i=0, capacity=5). We consider item 0 (weight=2, value=15). Two choices: take it or skip it.
Step 2: Take item 0. Profit so far includes 15. Capacity drops from 5 to 3. Since items are reusable, we stay at i=0. Now solve(0, 3).
Step 3: At solve(0, 3), take item 0 again. Profit adds 15. Capacity drops from 3 to 1. Now solve(0, 1).
Step 4: At solve(0, 1), item 0 weighs 2 but capacity is only 1. Cannot take it. Skip to item 1 → solve(1, 1).
Step 5: At solve(1, 1), item 1 weighs 3, exceeding capacity 1. Cannot take it. Skip → base case solve(2, 1). All items exhausted, return 0.
Step 6: solve(1, 1) = max(cannot take, 0) = 0. Bubble back up.
Step 7: solve(0, 1) = max(cannot take, 0) = 0. Back to solve(0, 3).
Step 8: solve(0, 3): take path gave 15 + solve(0, 1) = 15 + 0 = 15. Now try skip → solve(1, 3).
Step 9: At solve(1, 3), take item 1 (weight 3 fits capacity 3). Need solve(1, 0). With capacity 0, nothing fits → returns 0. Take profit = 25 + 0 = 25.
Step 10: solve(1, 3) skip → base case = 0. Result: max(25, 0) = 25.
Step 11: solve(0, 3) = max(15, 25) = 25. Back to solve(0, 5). Take path = 15 + 25 = 40.
Step 12: solve(0, 5) now tries skip → solve(1, 5). Item 1 (wt=3): take gives 25 + solve(1, 2). At solve(1, 2), item 1 wt=3 > 2, can't take. Base = 0. So solve(1, 2) = 0.
Step 13: solve(1, 5) = max(25 + 0, 0) = 25.
Step 14: solve(0, 5) = max(take=40, skip=25) = 40.
The optimal selection is one copy of item 0 (wt=2, val=15) and one copy of item 1 (wt=3, val=25), filling the knapsack exactly.
Unbounded Knapsack — Recursive Exploration Tree — Watch how the recursion explores every take/skip branch, diving deep before backtracking, to find the maximum-profit combination.
Algorithm
- Define a recursive function
solve(i, capacity)that returns the maximum profit using items from indexionward with the given remaining capacity. - Base case: If
i == n(all items considered), return 0. - Take choice: If
wt[i] <= capacity, computetake = val[i] + solve(i, capacity - wt[i]). Note: we passi(noti+1) because the item can be reused. - Skip choice: Compute
skip = solve(i + 1, capacity)to move past the current item. - Return
max(take, skip). - The answer is
solve(0, capacity).
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int solve(int i, int capacity, vector<int>& val, vector<int>& wt) {
if (i == (int)val.size()) return 0;
int take = 0;
if (wt[i] <= capacity) {
take = val[i] + solve(i, capacity - wt[i], val, wt);
}
int skip = solve(i + 1, capacity, val, wt);
return max(take, skip);
}
int knapSack(int capacity, vector<int>& val, vector<int>& wt) {
return solve(0, capacity, val, wt);
}
};class Solution:
def solve(self, i, capacity, val, wt):
if i == len(val):
return 0
take = 0
if wt[i] <= capacity:
take = val[i] + self.solve(i, capacity - wt[i], val, wt)
skip = self.solve(i + 1, capacity, val, wt)
return max(take, skip)
def knapSack(self, capacity, val, wt):
return self.solve(0, capacity, val, wt)class Solution {
int solve(int i, int capacity, int[] val, int[] wt) {
if (i == val.length) return 0;
int take = 0;
if (wt[i] <= capacity) {
take = val[i] + solve(i, capacity - wt[i], val, wt);
}
int skip = solve(i + 1, capacity, val, wt);
return Math.max(take, skip);
}
int knapSack(int capacity, int[] val, int[] wt) {
return solve(0, capacity, val, wt);
}
}Complexity Analysis
Time Complexity: O(2^(n + capacity))
In the worst case, each call branches into two sub-calls: take (which may repeat many times for light items) and skip. For an item with weight 1 and large capacity, the take branch alone generates up to capacity levels of recursion, each of which also spawns skip branches. The recursion tree grows exponentially.
Space Complexity: O(capacity)
The maximum depth of the recursion stack is bounded by capacity because each take call reduces the capacity by at least 1 (since wt[i] ≥ 1). The skip calls add at most n depth on top, but capacity dominates when capacity >> n.
Why This Approach Is Not Efficient
The brute-force recursion explores an exponentially large tree. With n up to 1000 items and capacity up to 1000, the number of recursive calls becomes astronomical — far beyond what any computer can handle within time limits.
The root cause of the inefficiency is overlapping subproblems. The same (item_index, remaining_capacity) pair is recomputed many times across different branches of the tree. For instance, solve(1, 3) might be needed when we take item 0 once from capacity 5, and also when we take item 0 twice from capacity 7. Both paths lead to the exact same subproblem, yet the brute force solves it from scratch each time.
Since there are only n × (capacity + 1) unique (i, cap) states, and our brute force revisits them exponentially, we are doing enormous redundant work. This observation directly motivates memoization: store each subproblem's result the first time we compute it, and look it up instantly for all subsequent calls.
Better Approach - Memoization (Top-Down DP)
Intuition
The brute force explores the same subproblem many times. Memoization fixes this by adding a cache — a 2D table memo[i][cap] — that stores the result of each (item_index, remaining_capacity) pair the first time it is computed.
Think of it like a notebook. Before solving any subproblem, you check your notebook: "Have I solved this exact question before?" If yes, you read the answer directly. If no, you solve it, write the answer in your notebook, and return it.
The recursion structure stays identical to the brute force. The only addition is:
- Before computing, check
memo[i][cap]. If it is not -1, return the stored value. - After computing, store the result in
memo[i][cap].
This simple change transforms the exponential brute force into a polynomial-time algorithm. Each of the n × (capacity + 1) states is computed exactly once, and each computation does O(1) work.
Step-by-Step Explanation
Let's trace with the same example: val = [15, 25], wt = [2, 3], capacity = 5. We use a 2×6 memo table (2 items × capacities 0 through 5), initialized to -1 (uncomputed).
Step 1: Call solve(0, 5). memo[0][5] = -1, so compute it. Recurse into take → solve(0, 3).
Step 2: solve(0, 3). memo[0][3] = -1. Take → solve(0, 1). memo[0][1] = -1. Can't take item 0 (wt=2>1). Skip → solve(1, 1). memo[1][1] = -1.
Step 3: solve(1, 1): wt[1]=3 > 1, can't take. Skip → base = 0. Store memo[1][1] = 0.
Step 4: solve(0, 1): skip = memo[1][1] = 0. Result = 0. Store memo[0][1] = 0.
Step 5: Back at solve(0, 3). Take = 15 + memo[0][1] = 15. Now skip → solve(1, 3). memo[1][3] = -1.
Step 6: solve(1, 3): take item 1. Need solve(1, 0). memo[1][0] = -1. wt[1]=3>0, skip → base = 0. Store memo[1][0] = 0.
Step 7: solve(1, 3): take = 25 + memo[1][0] = 25. Skip → base = 0. Store memo[1][3] = max(25, 0) = 25.
Step 8: solve(0, 3): take = 15, skip = memo[1][3] = 25. Store memo[0][3] = max(15, 25) = 25.
Step 9: Back at solve(0, 5). Take = 15 + memo[0][3] = 40. Now skip → solve(1, 5). memo[1][5] = -1.
Step 10: solve(1, 5): take item 1. Need solve(1, 2). memo[1][2] = -1. wt[1]=3>2, skip → base = 0. Store memo[1][2] = 0.
Step 11: solve(1, 5): take = 25 + memo[1][2] = 25. Skip → base = 0. Store memo[1][5] = max(25, 0) = 25.
Step 12: solve(0, 5): take = 40, skip = memo[1][5] = 25. Store memo[0][5] = max(40, 25) = 40.
Answer: 40. Each subproblem was solved exactly once and cached for reuse.
Memoization — 2D Cache Filling (Top-Down) — Watch how the memo table fills on demand as the recursion encounters each unique (item, capacity) pair for the first time.
Algorithm
- Create a 2D memo table of size
n × (capacity + 1), initialized to -1. - Define
solve(i, cap)recursively:- If
i == n, return 0 (no items left). - If
memo[i][cap] != -1, returnmemo[i][cap](already computed). - Compute
take = val[i] + solve(i, cap - wt[i])ifwt[i] <= cap. - Compute
skip = solve(i + 1, cap). - Store and return
memo[i][cap] = max(take, skip).
- If
- The answer is
solve(0, capacity).
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int solve(int i, int capacity, vector<int>& val, vector<int>& wt,
vector<vector<int>>& memo) {
if (i == (int)val.size()) return 0;
if (memo[i][capacity] != -1) return memo[i][capacity];
int take = 0;
if (wt[i] <= capacity) {
take = val[i] + solve(i, capacity - wt[i], val, wt, memo);
}
int skip = solve(i + 1, capacity, val, wt, memo);
return memo[i][capacity] = max(take, skip);
}
int knapSack(int capacity, vector<int>& val, vector<int>& wt) {
int n = val.size();
vector<vector<int>> memo(n, vector<int>(capacity + 1, -1));
return solve(0, capacity, val, wt, memo);
}
};class Solution:
def solve(self, i, capacity, val, wt, memo):
if i == len(val):
return 0
if memo[i][capacity] != -1:
return memo[i][capacity]
take = 0
if wt[i] <= capacity:
take = val[i] + self.solve(i, capacity - wt[i], val, wt, memo)
skip = self.solve(i + 1, capacity, val, wt, memo)
memo[i][capacity] = max(take, skip)
return memo[i][capacity]
def knapSack(self, capacity, val, wt):
n = len(val)
memo = [[-1] * (capacity + 1) for _ in range(n)]
return self.solve(0, capacity, val, wt, memo)import java.util.Arrays;
class Solution {
int solve(int i, int capacity, int[] val, int[] wt, int[][] memo) {
if (i == val.length) return 0;
if (memo[i][capacity] != -1) return memo[i][capacity];
int take = 0;
if (wt[i] <= capacity) {
take = val[i] + solve(i, capacity - wt[i], val, wt, memo);
}
int skip = solve(i + 1, capacity, val, wt, memo);
return memo[i][capacity] = Math.max(take, skip);
}
int knapSack(int capacity, int[] val, int[] wt) {
int n = val.length;
int[][] memo = new int[n][capacity + 1];
for (int[] row : memo) Arrays.fill(row, -1);
return solve(0, capacity, val, wt, memo);
}
}Complexity Analysis
Time Complexity: O(n × capacity)
There are n × (capacity + 1) unique states in the memo table. Each state is computed at most once, and each computation performs O(1) work (a comparison and a max operation). Therefore, total work is O(n × capacity).
Space Complexity: O(n × capacity)
The 2D memo table occupies n × (capacity + 1) cells. Additionally, the recursion stack can be as deep as O(n + capacity) in the worst case — O(capacity) for consecutive take calls on item 0, plus O(n) for skip calls down the item list. The table dominates, giving O(n × capacity) overall.
Why This Approach Is Not Efficient
Memoization reduces the time from exponential to O(n × capacity), which is a massive improvement. However, it has two drawbacks:
1. Space overhead: The 2D memo table uses O(n × capacity) space. With n = 1000 and capacity = 1000, that is 1,000,000 integers — approximately 4 MB. While manageable, this is more space than necessary.
2. Recursion overhead: The top-down approach relies on the call stack. Deep recursion chains (e.g., taking item 0 with weight 1 repeatedly for capacity 1000) create stack depths up to 1000, risking stack overflow in some environments. Each recursive call also carries function-call overhead.
Key insight for improvement: Look at the dependency structure. In the unbounded knapsack, dp[i][cap] depends on dp[i][cap - wt[i]] (same row, smaller capacity) and dp[i+1][cap] (next row, same capacity). Since we only look at the current row and the next row, we can build the table iteratively from bottom to top. Even better, because the "take" dependency dp[i][cap - wt[i]] reads from the same row at a smaller capacity (already computed left-to-right), we can collapse the entire 2D table into a single 1D array.
Optimal Approach - Space Optimized Tabulation (1D DP)
Intuition
Instead of a 2D table and recursion, we use a single 1D array dp where dp[j] represents the maximum profit achievable with a knapsack of capacity j, considering all items processed so far.
Imagine you have a row of boxes labeled 0 through capacity. Each box stores the best profit for that capacity. You process items one by one. For each item, you walk left-to-right through the boxes. At each box j, you ask: "Can I improve the profit by including this item?" If including the item gives a better result than what is already in the box, you update it.
The magic of the unbounded knapsack lies in the left-to-right traversal. When you compute dp[j], the value dp[j - wt[i]] may already have been updated during this same pass — meaning it already accounts for including item i. This naturally allows multiple copies of the same item without any extra logic.
This is the critical difference from the 0/1 knapsack (where you traverse right-to-left to prevent reusing an item). Here, reuse is exactly what we want, so left-to-right is correct.
Step-by-Step Explanation
Let's trace with val = [15, 25], wt = [2, 3], capacity = 5:
Initialize dp = [0, 0, 0, 0, 0, 0]. dp[j] = 0 means zero profit for every capacity initially.
Processing item 0 (weight = 2, value = 15):
Step 1: j = 2: Can we include item 0? Yes (wt=2 ≤ 2). take = 15 + dp[2-2] = 15 + dp[0] = 15 + 0 = 15. Current dp[2] = 0. dp[2] = max(0, 15) = 15.
Step 2: j = 3: take = 15 + dp[3-2] = 15 + dp[1] = 15 + 0 = 15. dp[3] = max(0, 15) = 15.
Step 3: j = 4: take = 15 + dp[4-2] = 15 + dp[2] = 15 + 15 = 30. Notice dp[2] was already updated to 15 in Step 1 — this means we are effectively taking item 0 twice! dp[4] = max(0, 30) = 30.
Step 4: j = 5: take = 15 + dp[5-2] = 15 + dp[3] = 15 + 15 = 30. dp[5] = max(0, 30) = 30.
After item 0: dp = [0, 0, 15, 15, 30, 30]
Processing item 1 (weight = 3, value = 25):
Step 5: j = 3: take = 25 + dp[3-3] = 25 + dp[0] = 25 + 0 = 25. Current dp[3] = 15. dp[3] = max(15, 25) = 25. Item 1 alone is more valuable than item 0 alone at capacity 3!
Step 6: j = 4: take = 25 + dp[4-3] = 25 + dp[1] = 25 + 0 = 25. Current dp[4] = 30. dp[4] = max(30, 25) = 30. No update — two copies of item 0 (profit 30) still beats one item 1 (profit 25) at capacity 4.
Step 7: j = 5: take = 25 + dp[5-3] = 25 + dp[2] = 25 + 15 = 40. Current dp[5] = 30. dp[5] = max(30, 40) = 40. One item 1 (25) plus one item 0 (15) totals 40, beating two item 0s (30).
Final dp = [0, 0, 15, 25, 30, 40]
Answer: dp[5] = 40.
Space-Optimized 1D DP — Left-to-Right Table Filling — Watch how a single 1D array is updated left-to-right for each item. Left-to-right traversal allows values updated earlier in the same pass to be reused, enabling multiple copies of the same item.
Algorithm
- Create a 1D array
dpof sizecapacity + 1, initialized to 0. - For each item
ifrom 0 to n-1:- For each capacity
jfromwt[i]tocapacity(left to right):- Compute
take = val[i] + dp[j - wt[i]] - Update
dp[j] = max(dp[j], take)
- Compute
- For each capacity
- Return
dp[capacity].
Why left-to-right? When computing dp[j], the value dp[j - wt[i]] may already reflect item i being included (updated earlier in the same pass). This means item i can be included multiple times — exactly what unbounded knapsack requires. In contrast, 0/1 knapsack iterates right-to-left to prevent this reuse.
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int knapSack(int capacity, vector<int>& val, vector<int>& wt) {
int n = val.size();
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
for (int j = wt[i]; j <= capacity; j++) {
dp[j] = max(dp[j], val[i] + dp[j - wt[i]]);
}
}
return dp[capacity];
}
};class Solution:
def knapSack(self, capacity, val, wt):
n = len(val)
dp = [0] * (capacity + 1)
for i in range(n):
for j in range(wt[i], capacity + 1):
dp[j] = max(dp[j], val[i] + dp[j - wt[i]])
return dp[capacity]class Solution {
int knapSack(int capacity, int[] val, int[] wt) {
int n = val.length;
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int j = wt[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], val[i] + dp[j - wt[i]]);
}
}
return dp[capacity];
}
}Complexity Analysis
Time Complexity: O(n × capacity)
The outer loop runs n times (once per item). The inner loop runs at most capacity times per item. Each iteration does O(1) work: one addition, one comparison, one potential assignment. Total: O(n × capacity).
Space Complexity: O(capacity)
We use a single 1D array of size capacity + 1. No recursion stack, no 2D table. This is the minimum space needed for this problem class — we must at least store the result for each capacity from 0 to capacity.
Compared to memoization's O(n × capacity) space, this is a factor of n improvement. With n = 1000 and capacity = 1000, memoization uses ~4 MB while this uses only ~4 KB.