323. Unbounded Knapsack (Repetition of Items Allowed)

Given n item types, each with a weight and a value, and a knapsack of capacity W, find the maximum total value obtainable by picking items with unlimited repetition allowed for every type (any number of copies of any item, as long as total weight doesn't exceed W).

Input: The first line contains an integer n. The second line contains n space-separated integers, the item weights. The third line contains n space-separated integers, the item values. The fourth line contains an integer W, the knapsack capacity. Output: Print a single integer - the maximum total value achievable with unlimited repetition of items.

1 <= n <= 1000, 1 <= W <= 10^4

This single-array-reused-within-the-same-pass technique is the exact defining difference from 0/1 knapsack - recognizing this one-line difference is what separates 'bounded' and 'unbounded' variants of nearly every knapsack-family problem.

Choose items (unlimited repetition allowed per type) to maximize value within a weight capacity. Brute force: Try every possible combination of item counts (how many of each type) summing to at most W - this can be combinatorially large, impractical for bigger capacities. Optimised: Since items can repeat, dp[w] only needs to look back at SMALLER capacities within the SAME single array (rather than a separate row per item, as 0/1 knapsack needs) - this single-array update rule is precisely what allows the same item to be 'reused' as many times as beneficial.

Define a recursive function on remaining capacity that, at each call, tries including one more copy of every item type whose weight fits (recursing on capacity minus that weight, plus that item's value) and also tries stopping, returning the best value found across all these branches. Since the same remaining-capacity value can be reached through many different combinations of item choices, and each is recomputed independently, the number of recursive calls grows exponentially with capacity. Time: O(2^W) Space: O(W)

Build a single array dp of size W+1 where dp[w] is the best value achievable with capacity exactly w, initialized to 0. Fill it in increasing order of w from 1 to W, and for each w try every item type i, updating dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) whenever weight[i] <= w. Because dp[w - weight[i]] may itself already include item i (unlike the 0/1 knapsack, where you'd use the previous row), a single forward pass through capacities naturally allows unlimited repetition of each item without recursion overhead or extra dimensions. Time: O(n*W) Space: O(W)

Use the same recursive formulation as the brute approach, but cache the best achievable value for each remaining-capacity value the first time it's computed, and return the cached result on any later call with that same capacity. Since capacity only ranges from 0 to W and there are n item types to try at each capacity, this collapses the exponential tree down to at most n*W distinct subproblems, each solved once. Time: O(n*W) Space: O(W)

1. dp[w] = best value achievable with capacity exactly up to w. 2. For each capacity w, try every item i: if it fits, dp[w] = max(dp[w], dp[w-weight[i]] + value[i]). 3. Crucially, dp[w-weight[i]] is looked up from the SAME pass (not a previous item's separate row) - this is exactly what allows unlimited repetition of any item.

Time: O(n * W) - for each of the W capacities, trying all n item types. Space: O(W), for the single 1D dp array.

Test when every item's weight exceeds W (answer 0), W = 0, and n up to 1000 with W up to 10^4 for performance.

Be ready to contrast this explicitly with 0/1 Knapsack's space-optimized version - the ONLY difference is processing capacity in INCREASING order here (allowing reuse) versus DECREASING order there (preventing reuse) - a subtle but critical distinction.