Unbounded Knapsack

Unbounded knapsack maximizes profit by choosing, for each capacity from 1 up to C, whether re-using an already-solved smaller-capacity answer (allowing the current item to be picked again) beats leaving that capacity's best answer alone — because an item can be reused, the recurrence reduces capacity but never removes the item from consideration.

Recognize the pattern

• "Unlimited supply" / "as many times as you want" / "minimum coins to make amount" / "rod cutting" / "ways to make change" phrasing.
• You pick from a fixed small set of item types repeatedly to fill a capacity/target exactly or at most.
• Contrast with 0/1 knapsack: there the phrase is "each item at most once".

Brute force → optimal

Brute force: recursion trying, at every capacity, either skip item i or take item i and recurse on capacity - weight[i] while staying on the same item index i (not i-1, since reuse is allowed). Without memoization this branches into overlapping subproblems: T(C) = T(C-w) + T(C) style calls repeat the same (i, capacity) pairs exponentially — O(2^C) in the worst case, O(C) space for the call stack.

Optimal: bottom-up DP over a 1-D array dp[0..C], since each item may repeat, we deliberately let dp[cap] reuse a value just written in the same pass (unlike 0/1 knapsack, which must iterate capacity in reverse to forbid reuse). Iterate capacity forward: dp[cap] = max(dp[cap], dp[cap-weight[i]] + profit[i]).

Complexity, derived

Two nested loops: for each of the N item types, for each capacity 1..C we do O(1) work (one comparison, one addition). Total operations = N × C ⇒ time O(N·C). Space: one dp array of size C+1 ⇒ O(C) (no per-item row needed because forward iteration already permits reuse within the same item's row, and rows across items only ever improve dp monotonically, so a single rolling array suffices). Brute force without memo redoes each (item-index, capacity) combination up to C times per level — recurrence R(C) = R(C-1) + R(C-2) + ... in the worst case gives exponential blowup, i.e., O(2^C) time, O(C) stack space.

Worked example

Weights {1,2,3}, Profits {15,20,50}, Capacity 5. dp[0..5] starts at 0. Process item Apple (w=1,p=15) forward:

At cap=5 during Melon's pass: dp[5] = max(dp[5]=75, dp[5-3]+50 = dp[2]+50 = 30+50 = 80) → 80, matching "2 Apples + 1 Melon".

Java

int unboundedKnapsack(int[] weights, int[] profits, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < n; i++) {
        for (int cap = weights[i]; cap <= capacity; cap++) { // forward!
            dp[cap] = Math.max(dp[cap], dp[cap - weights[i]] + profits[i]);
        }
    }
    return dp[capacity];
}

Pitfalls

• Iterating capacity backward (0/1 habit) silently caps each item to one use — a subtle bug that only surfaces on inputs needing repeats.
• Not initializing dp[0]=0 explicitly when profits can be negative-adjacent (usually fine here since default 0 is correct base case).
• Confusing this with "coin change count ways" (which needs a different loop nesting — outer over coins for combinations, outer over amount for permutations) — the nesting order matters for that variant, not for this max-profit variant.
• Off-by-one on the inner loop start (must start at weights[i], not 0, else negative index).
• A zero-weight item with positive profit makes the optimum unbounded (infinite): the forward pass keeps re-adding its profit at the same capacity forever. Guard against weight-0 items (reject them, or treat as a free one-time profit) before running the DP.

When to use / when NOT — trade-offs

Use unbounded knapsack DP when items are reusable and you need the true optimum over all repeat-combinations in O(N·C) time/O(C) space — far better than the brute-force exponential enumeration. Do NOT use it if items are limited-supply (each has a count k) — that's bounded knapsack, solved by binary/log splitting each item into 0/1 items (O(N·C·log k)) or a monotonic-deque optimization. If C is huge (e.g., 10^9) but N is small and weights are small, unbounded knapsack DP is infeasible; consider a greedy/number-theory approach (Chicken McNugget / Frobenius, or meet-in-the-middle for the residues) instead.

Takeaways

• The only code change from 0/1 knapsack is loop direction: forward = reuse allowed (unbounded), backward = reuse forbidden (0/1).
• Complexity is O(N·C) time, O(C) space, derived directly from the two nested loops over items and capacities.
• Trace the array pass-by-pass — the dp value at a capacity can jump within the same item's pass because it's allowed to reference itself.

Recall: Why does making the capacity loop go forward (instead of backward) let the same item be used more than once?

Adapted from the classic "Unbounded Knapsack" formulation (Educative-style DP course material); complexity and forward/backward loop-direction analysis derived from first principles for this guide.