Dynamic Programming - DSA: Unbounded Knapsack | 1-D Array Space Optimised Approach

1. Problem Statement & Context

In this chapter, we tackle the classic Unbounded Knapsack problem (Problem 23 in the Dynamic Programming series). Building directly upon the concepts learned in 0/1 Knapsack (DP 19) and Coin Change (DP 20/22), this problem introduces a crucial twist in item selection rules.

The Core Scenario

Imagine a thief entering a house with a bag that has a maximum weight capacity $W$ (e.g., $W = 10$). The thief encounters several items, each characterized by a specific weight and a corresponding profit value.

0/1 Knapsack vs. Unbounded Knapsack

• 0/1 Knapsack: Each item can be picked at most once (binary choice: take or not take).
• Unbounded Knapsack: There is an infinite supply of every item. You can pick the exact same item as many times as your bag's weight capacity allows.

Real-Life Analogy: The Unlimited Buffet Plate

Real-Life Analogy: Think of an unbounded buffet where plates have a strict weight limit. Unlike a fixed-plate event where you can only take one serving of steak and one serving of lobster (0/1 Knapsack), an unbounded buffet lets you stack your plate with five servings of the exact same dessert as long as you do not exceed your overall tray weight limit. Your goal is to maximize the total satisfaction (value) packed onto the plate.

2. Core Mental Model & Exploration Strategy

To solve any knapsack variation, we follow the standard dynamic programming design pattern:

1. Express the problem in terms of parameters: Usually (index, target_weight).
2. Explore all possible choices: Make decisions at every index.
3. Aggregate results: Return the maximum value generated across all choices.

The Infinite Supply Decision Rule

When standing at a given index with a remaining bag weight W:

• Not Take: We skip the current item, move to index - 1, and the bag weight remains W.
• Take: We pick the item (provided its weight $\le W$). Because we have an infinite supply, we stay at the same index (index) for the next recursive call, and the bag weight is reduced by the item's weight (W - wt[index]).

3. Recursive Formulation & Recurrence Relations

Let f(index, W) represent the maximum value attainable using items from 0 to index with a remaining bag weight W.

1. Not Take Case

int notTake = 0 + f(index - 1, W, val, wt);

2. Take Case (Conditional on Weight)

int take = INT_MIN;
if (wt[index] <= W) {
    take = val[index] + f(index, W - wt[index], val, wt); // Notice index does NOT decrement!
}

3. Combining Choices

return max(take, notTake);

4. Base Case Derivation

In standard 0/1 Knapsack, the base case evaluates index == 0. In Unbounded Knapsack, when we reach index == 0, we are at the very first item, which has an infinite supply.

If our remaining bag weight is $W$, how many times can we pick item 0?

Thus, the base case return value is:

if (index == 0) {
    return (W / wt[0]) * val[0];
}

5. Complete Recursive Implementation

Below is the pure recursive implementation capturing the exact logic described:

#include <bits/stdc++.h>
using namespace std;

int unboundedKnapsackUtil(int index, int W, vector<int>& val, vector<int>& wt) {
    // Base Case: Only one item left, take it as many times as weight permits
    if (index == 0) {
        return (W / wt[0]) * val[0];
    }
    
    // Option 1: Do not take current item
    int notTake = unboundedKnapsackUtil(index - 1, W, val, wt);
    
    // Option 2: Take current item (stay at same index due to infinite supply)
    int take = INT_MIN;
    if (wt[index] <= W) {
        take = val[index] + unboundedKnapsackUtil(index, W - wt[index], val, wt);
    }
    
    return max(take, notTake);
}

int unboundedKnapsack(int n, int W, vector<int>& val, vector<int>& wt) {
    return unboundedKnapsackUtil(n - 1, W, val, wt);
}

6. Memoization (Top-Down DP)

To eliminate overlapping subproblems, we introduce a 2D memoization table DP[n][W + 1] initialized to -1.

#include <bits/stdc++.h>
using namespace std;

int memoUtil(int index, int W, vector<int>& val, vector<int>& wt, vector<vector<int>>& dp) {
    if (index == 0) {
        return (W / wt[0]) * val[0];
    }
    
    if (dp[index][W] != -1) return dp[index][W];
    
    int notTake = memoUtil(index - 1, W, val, wt, dp);
    
    int take = INT_MIN;
    if (wt[index] <= W) {
        take = val[index] + memoUtil(index, W - wt[index], val, wt, dp);
    }
    
    return dp[index][W] = max(take, notTake);
}

int unboundedKnapsack(int n, int W, vector<int>& val, vector<int>& wt) {
    vector<vector<int>> dp(n, vector<int>(W + 1, -1));
    return memoUtil(n - 1, W, val, wt, dp);
}

• Time Complexity: $O(N \times W)$
• Space Complexity: $O(N \times W)$ [DP Table] + $O(W)$ [Recursion Stack Space]

7. Tabulation (Bottom-Up DP)

We convert the top-down recursion into an iterative bottom-up table.

Tabulation Steps:

1. Initialize a 2D DP table of size N x (W + 1).
2. Set up the base case for index = 0 across all weights from 0 to W.
3. Run nested loops: index from 1 to N - 1, and W from 0 to target W.
4. Copy the recurrence relation.

#include <bits/stdc++.h>
using namespace std;

int unboundedKnapsackTab(int n, int W, vector<int>& val, vector<int>& wt) {
    vector<vector<int>> dp(n, vector<int>(W + 1, 0));
    
    // Base Case initialization for index 0
    for (int w = 0; w <= W; w++) {
        dp[0][w] = (w / wt[0]) * val[0];
    }
    
    // Fill remaining rows
    for (int index = 1; index < n; index++) {
        for (int w = 0; w <= W; w++) {
            int notTake = dp[index - 1][w];
            
            int take = INT_MIN;
            if (wt[index] <= w) {
                take = val[index] + dp[index][w - wt[index]]; // Notice dp[index] (current row)
            }
            
            dp[index][w] = max(take, notTake);
        }
    }
    
    return dp[n - 1][W];
}

8. Space Optimization: From 2-Rows to 1-D Array

Why is 1-D Optimization Possible Here?

In standard 0/1 Knapsack, computing dp[index][w] required looking at the strictly previous row (dp[index - 1][w - wt[index]]). That forced us to iterate backwards or maintain two separate rows (previous and current) to prevent overwriting data we still needed.

In Unbounded Knapsack, look closely at the take term:

Notice that we access dp[index]—the current row itself, not the previous row! Because we are allowed to use an item multiple times, we need the freshly updated values from the current row computed at smaller weights.

The 1-D Array Mechanics

• We maintain a single 1D array prev (representing the current working row).
• As we iterate weights from 0 up to W, any value we calculate at w is immediately placed into prev[w].
• When the inner loop reaches a larger weight w - wt[index], prev[w - wt[index]] already contains the optimal value including the current item (since we move forward from left to right).

Single 1-D Array Evolution (Left to Right):
[ 0 | 1 | 2 | 3 | 4 | ... | W ]
  ^                   ^
  |                   |
Computed earlier    Computing current (can safely pull from left/back)

9. Final 1-D Space-Optimized Implementation

Here is the production-ready, highly optimized C++ solution using a single 1-D array:

#include <bits/stdc++.h>
using namespace std;

int unboundedKnapsackOptimized(int n, int W, vector<int>& val, vector<int>& wt) {
    vector<int> prev(W + 1, 0);
    
    // Base case initialization for index 0
    for (int w = 0; w <= W; w++) {
        prev[w] = (w / wt[0]) * val[0];
    }
    
    // Iterate through all items
    for (int index = 1; index < n; index++) {
        for (int w = 0; w <= W; w++) {
            int notTake = prev[w];
            
            int take = INT_MIN;
            if (wt[index] <= w) {
                // Pulls from the same row because of infinite supply / current row dependency
                take = val[index] + prev[w - wt[index]];
            }
            
            prev[w] = max(take, notTake);
        }
    }
    
    return prev[W];
}

Complexity Analysis

• Time Complexity: $O(N \times W)$ — We visit each cell in the $N \times (W + 1)$ grid exactly once.
• Space Complexity: $O(W)$ — Reduced from $O(N \times W)$ down to a single 1-D array of size $W + 1$.

10. Summary and Key Takeaways

• Infinite Supply Distinction: Unlike 0/1 Knapsack where picking an item moves you to index - 1, Unbounded Knapsack keeps you at the same index (index) because items can be chosen repeatedly.
• Base Case Formula: For index == 0, the maximum value is calculated using integer division: $\lfloor \frac{W}{\text{wt}[0]} \rfloor \times \text{val}[0]$.
• Recurrence Structure:
  • $\text{notTake} = \text{dp}[index - 1][w]$
  • $\text{take} = \text{val}[index] + \text{dp}[index][w - \text{wt}[index]]$
• Space Optimization Breakthrough: Because the take state queries the current row rather than the strictly previous row, space can be optimized from 2D down to a 1-D array processed from left to right.
• Progressive Optimization Journey: Recursion (Exponential Time) $\rightarrow$ Memoization $O(N \times W)$ time & space $\rightarrow$ Tabulation 2D $\rightarrow$ 2-Array Optimization $\rightarrow$ 1-D Array Optimal Solution ($O(W)$ Space).