Log inSign up
mediumGeeksforGeeksNot Started

Unbounded Knapsack

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a knapsack of capacity w and n items, each item having a weight wt[i] and a value val[i].

Find the maximum value that can be put into the knapsack.

You can put unlimited copies of any item into the knapsack.

### Example 1 - Input: w = 100, val = [1, 30], wt = [1, 50] - Output: 100 - Explanation: Pick 100 copies of item 1 (weight 1, value 1): 100 * 1 = 100. Alternatively, pick 2 copies of item 2 (weight 50, value 30): 2 * 30 = 60. Max is 100.

### Example 2 - Input: w = 8, val = [10, 40, 50, 70], wt = [1, 3, 4, 5] - Output: 110 - Explanation: Take item 2 (wt 3, val 40) + item 4 (wt 5, val 70) = 40 + 70 = 110.

Constraints:

  • 1 <= n, w <= 1000
  • 1 <= val[i], wt[i] <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mechanical difference between 0/1 Knapsack (reverse loop) and Unbounded Knapsack (forward loop).
  • Space-optimize to a single 1D array of size w + 1.
  • Formulate transitions for reusable items.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Knapsack capacity optimization.
  • Infinite / unlimited supply of each item.

Algorithmic Decision Tree:

  • Forward 1D capacity loop enables repeated item reuse.

Connected Patterns:

Coin ChangeCoin Change IIRod Cutting

1. Recursive Branching

Intuition

Recursively try taking each item that fits in the remaining capacity, branching into infinite combinations.

Algorithm

  1. Define solve(remW).
  2. If remW <= 0, return 0.
  3. Initialize maxVal = 0.
  4. For each item i from 0 to n - 1:
  5. If wt[i] <= remW:
  6. maxVal = max(maxVal, val[i] + solve(remW - wt[i])).
  7. Return maxVal.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int remW, int n, const vector<int>& val, const vector<int>& wt) {
9 if (remW <= 0) return 0;
10 int maxVal = 0;
11 for (int i = 0; i < n; ++i) {
12 if (wt[i] <= remW) {
13 maxVal = max(maxVal, val[i] + solve(remW - wt[i], n, val, wt));
14 }
15 }
16 return maxVal;
17 }
18public:
19 int knapSack(int n, int w, vector<int>& val, vector<int>& wt) {
20 return solve(w, n, val, wt);
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<int> val = {10, 40, 50, 70};
27 vector<int> wt = {1, 3, 4, 5};
28 cout << "Max Knapsack Value: " << sol.knapSack(4, 8, val, wt) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(n^w)
  • Space complexity: O(w) call stack

2. Memoized Top-Down DP

Intuition

Store results of remaining capacity subproblems in a 1D memo array of size w + 1.

Algorithm

  1. Initialize memo array of size w + 1 with -1.
  2. In solve(remW): return memo[remW] if already computed.
  3. Iterate across all items, update maxVal.
  4. Store in memo[remW] and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int remW, int n, const vector<int>& val, const vector<int>& wt, vector<int>& memo) {
9 if (remW <= 0) return 0;
10 if (memo[remW] != -1) return memo[remW];
11
12 int maxVal = 0;
13 for (int i = 0; i < n; ++i) {
14 if (wt[i] <= remW) {
15 maxVal = max(maxVal, val[i] + solve(remW - wt[i], n, val, wt, memo));
16 }
17 }
18
19 return memo[remW] = maxVal;
20 }
21public:
22 int knapSack(int n, int w, vector<int>& val, vector<int>& wt) {
23 vector<int> memo(w + 1, -1);
24 return solve(w, n, val, wt, memo);
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> val = {10, 40, 50, 70};
31 vector<int> wt = {1, 3, 4, 5};
32 cout << "Max Knapsack Value: " << sol.knapSack(4, 8, val, wt) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(n * w)
  • Space complexity: O(w)

3. 1D Forward Tabulation (O(n * w) Time, O(w) Space)

Intuition

Use a single 1D array of size w + 1. For each item, iterate capacity forward from wt[i] to w.

Algorithm

  1. Initialize array dp of size w + 1 with 0.
  2. For i from 0 to n - 1:
  3. For cap from wt[i] to w:
  4. dp[cap] = max(dp[cap], val[i] + dp[cap - wt[i]]).
  5. Return dp[w].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int knapSack(int n, int w, vector<int>& val, vector<int>& wt) {
10 vector<int> dp(w + 1, 0);
11
12 for (int i = 0; i < n; ++i) {
13 for (int cap = wt[i]; cap <= w; ++cap) {
14 dp[cap] = max(dp[cap], val[i] + dp[cap - wt[i]]);
15 }
16 }
17
18 return dp[w];
19 }
20};
21
22int main() {
23 Solution sol;
24 vector<int> val = {10, 40, 50, 70};
25 vector<int> wt = {1, 3, 4, 5};
26 cout << "Max Knapsack Value: " << sol.knapSack(4, 8, val, wt) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n * w)
  • Space complexity: O(w)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive BranchingO(n^w)O(w)Exhaustive branching over all items.Infinite branching potential
2.Memoized DPO(n * w)O(w)Cache capacities in memo array.Call stack
3.1D Forward TabulationOptimalO(n * w)O(w)Iterate capacity forward to naturally allow repeated item reuse.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating backwards (which turns Unbounded Knapsack into 0/1 Knapsack).

Pitfall 2:

Mixing up indices between value array and weight array.

Crucial Edge Cases to Validate:

  • Capacity w = 0: Returns 0.
  • Item with wt[i] > w: Skipped automatically.
  • Item with wt[i] = 1: Can fill the entire knapsack with w copies.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly articulate why forward loop iteration creates unbounded reuse. It is one of the most classic dynamic programming concepts interviewers look for.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the crucial loop direction difference between 0/1 Knapsack and Unbounded Knapsack when using a 1D DP array?

Back to DSA Sheet