Unbounded Knapsack - Theory

Problem Introduction

Definition

Given n items with weights wt[] and values val[], and a knapsack of capacity W, the Unbounded Knapsack Problem maximizes the total value in the knapsack by including items any number of times (each item is infinitely available).

Real-World Significance

Coin change systems (maximize value with unlimited coin denominations)
Resource allocation (e.g., cutting rods to maximize profit)
Inventory restocking without quantity limits

Classic Formulation

Input:  
  wt[] = {2, 3, 5}         // Item weights  
  val[] = {50, 100, 140}   // Item values  
  W = 10                   // Knapsack capacity  
Output: 550                // Max value = 5 * val[0] (5 items of weight 2, value 50)

Key Difference from 0/1 Knapsack

Aspect	0/1 Knapsack	Unbounded Knapsack
Item Usage	Each item used at most once	Items used unlimited times
DP Transition	After taking, move to the next item	After taking, stay on same item
Real-World Analogy	Packing unique items in a suitcase	Buying unlimited stock of products

Practical Use Cases

Coin Change: Maximize value with unlimited coins
Rod Cutting: Maximize profit by cutting rods of different lengths/prices

Solution Approaches

1. Recursion

Intuition:
For each item, decide to take it (and stay on it) or skip it (move to next).

Recursive Formula:

maxValue(i, W) = 
  if (W == 0 || i == n): 0
  else if (wt[i] > W): maxValue(i+1, W)
  else: max( 
      val[i] + maxValue(i, W - wt[i]), // Take item (stay at `i`)
      maxValue(i+1, W)                 // Skip item (move to `i+1`)
  )

Java Code:

int knapsack(int[] wt, int[] val, int i, int W) {
    if (i == wt.length || W == 0) return 0;
    if (wt[i] > W) return knapsack(wt, val, i + 1, W);
    else {
        int take = val[i] + knapsack(wt, val, i, W - wt[i]);
        int skip = knapsack(wt, val, i + 1, W);
        return Math.max(take, skip);
    }
}
// Time: O(2^W), Space: O(W)

2. Memoization (Top-Down)

Intuition:
Cache results of overlapping subproblems in a 2D array.

DP State:
dp[i][w] = max value using first i items and capacity w.

Java Code:

int memoKnapsack(int[] wt, int[] val, int i, int W, Integer[][] dp) {
    if (i == wt.length || W == 0) return 0;
    if (dp[i][W] != null) return dp[i][W];

    if (wt[i] > W)
        dp[i][W] = memoKnapsack(wt, val, i + 1, W, dp);
    else {
        int take = val[i] + memoKnapsack(wt, val, i, W - wt[i], dp);
        int skip = memoKnapsack(wt, val, i + 1, W, dp);
        dp[i][W] = Math.max(take, skip);
    }
    return dp[i][W];
}
// Initialize dp = new Integer[n][W+1]
// Time: O(n*W), Space: O(n*W) + recursion stack

Dry Run Example (wt=[2,3], val=[50,100], W=4):

i \ w	2	3	4
0	50	50	100
1	50	100	100
2	0	0	0

Result: dp[0][4] = 100

3. Tabulation (Bottom-Up)

Intuition:
Fill a 2D DP table iteratively.

Base Case:
dp[i][0] = 0 for all i

Java Code:

int tabulateKnapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] > w)
                dp[i][w] = dp[i - 1][w]; // Skip
            else
                dp[i][w] = Math.max(
                    val[i - 1] + dp[i][w - wt[i - 1]], // Take
                    dp[i - 1][w]                        // Skip
                );
        }
    }
    return dp[n][W];
}
// Time: O(n*W), Space: O(n*W)

Dry Run Example (wt=[2,3], val=[50,100], W=4):

i \ w	2	3	4
0	0	0	0
1	50	100	150
2	50	100	150

4. Space Optimization (1D DP)

Intuition:
We can reuse the same array if we loop from w = 0 to W and consider all items at each capacity.

Java Code:

int optKnapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[] dp = new int[W + 1];
    
    for (int w = 0; w <= W; w++) {
        for (int i = 0; i < n; i++) {
            if (wt[i] <= w)
                dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }
    return dp[W];
}
// Time: O(n*W), Space: O(W)

Dry Run (wt=[2,3], val=[50,100], W=4):

w=0: dp[0] = 0
w=1: no item fits → dp[1] = 0
w=2: max(50 + dp[0]) = 50
w=3: max(50 + dp[1], 100 + dp[0]) = 100
w=4: max(50 + dp[2], 100 + dp[1]) = 100

Summary Table

Approach	Time Complexity	Space Complexity	Notes
Recursion	O(2^W)	O(W)	Naive and exponential
Memoization	O(n*W)	O(n*W)	Top-down with caching
Tabulation	O(n*W)	O(n*W)	Bottom-up, efficient
Space Optimized DP	O(n*W)	O(W)	Most optimal for large constraints

Key Insights

Pattern Recognition: Unbounded Knapsack allows reuse of the same item (unlike 0/1).
Interview Tip: Use 1D DP for space efficiency unless item tracking is needed.
Edge Cases:
- Zero capacity
- All items heavier than capacity
- Items with zero value

Real Interview Scenario

Problem:
You're an investor with unlimited shares of stocks (values = profit, weights = capital). Maximize profit given total capital W.

Solution:
Use Unbounded Knapsack with 1D DP approach.