Unbounded Knapsack: Dynamic Programming Solution

Two integer arrays, weights and values, describe the weight and value of every available item type. A knapsack has a maximum carrying capacity named capacity.

Choose any non-negative number of copies from every item type. Return the maximum total value possible without making the total weight exceed capacity.

Recursion

Every item creates two choices: skip the current item or take it. Skipping removes the current item type from further consideration, while taking earns its value and reduces the remaining capacity. Since the supply is unlimited, the same item type remains available after taking it.

The state solve(index, remainingCapacity) represents the maximum value obtainable using item types 0 through index. The initial call uses the last item and full capacity because all item types are available at the start.

Algorithm

• Define solve(index, remainingCapacity) as the maximum value obtainable from item types 0 through index, so each recursive call captures the complete decision state.

• Handle index == 0 by taking as many copies of the first item as the remaining capacity allows, because no other item type is available.

• Explore solve(index - 1, remainingCapacity) to skip the current item, leaving the full capacity for earlier item types.

• Initialize the take value with a very small sentinel so an overweight item cannot become the best choice.

• Explore the take branch with the same index after subtracting weights[index], because unlimited supply allows another copy of the current item.

• Add values[index] to the take result because one copy of the current item contributes its value.

• Return the larger of the take and skip results because the better valid choice gives the maximum value for the current state.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(2^D), where D = N + ⌊capacity / minWeight⌋ is the maximum recursion depth, because each recursive state can branch into take and skip choices.

Space Complexity: O(D), because the deepest active recursion path can contain at most D stack frames.

Memoization

Direct recursion can reach the same (index, remainingCapacity) state through different decision paths. Since the same state always produces the same maximum revenue, recalculating its entire subtree only repeats work.

Memoization keeps the same recursive decisions and adds a two-dimensional dp table. Each calculated state is stored using its item index and remaining capacity, allowing future calls to return the saved answer immediately. The take and skip choices remain unchanged.

Algorithm

• Create a dp table with N rows and capacity + 1 columns, filled with -1, so every uncalculated state has a clear marker.

• Keep the first-item base case unchanged because unlimited copies of the first item can still fill the remaining capacity.

• Return dp[index][remainingCapacity] on a cache hit because the same state always has the same maximum revenue.

• Evaluate the skip branch with index - 1 because the current item is excluded and only earlier item types remain available.

• Evaluate the take branch at the same index after checking that the item fits, because unlimited supply allows another copy of the current item.

• Store the maximum of the take and skip results in dp[index][remainingCapacity] so the completed state can be reused.

• Start from the last item and full capacity because the initial state must consider every available item type.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N × capacity), where N is the number of piece lengths, because at most N × (capacity + 1) states are calculated once with constant work per state.

Space Complexity: O(N × capacity + D), where D = N + ⌊capacity / minWeight⌋ is the maximum recursion depth, accounting for the dp table and recursion stack.

Tabulation

Memoization proves every answer depends on smaller item-capacity states. Tabulation computes the same states in a fixed order, removing recursive calls and the recursion stack.

The first row records values obtainable from unlimited copies of item 0. Later rows use the previous row for skipping and the current row at a smaller capacity for taking. Increasing capacity order makes every same-row take dependency ready before use.

Algorithm

• Create a dp table with n rows and capacity + 1 columns, because each cell represents the original (index, remainingCapacity) state.

• Fill row 0 with as many first-item copies as each capacity permits because every later skip transition needs a complete recursive base.

• Process item indices from 1 through n - 1, so the previous row already contains every skip answer.

• Scan capacities from 0 through capacity, because a take reads a smaller capacity from the current row.

• Read dp[index - 1][currentCapacity] as the skip value, preserving the answer formed without the current item.

• Read values[index] + dp[index][currentCapacity - weights[index]] after a fit check, allowing repeated current-item copies through the same row.

• Store the larger choice in dp[index][currentCapacity] so later states can reuse the optimum, then return the full-capacity cell from the last row.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N × capacity), where N is the number of piece lengths, because the N × (capacity + 1) table states each perform constant work.

Space Complexity: O(N × capacity), because the iterative dp table stores one answer for every piece-length and capacity pair, with no recursion stack.

Space Optimization

The tabulation transition needs a previous-row skip value and a current-row value at a smaller capacity. A single dp array can hold both pieces of information during an ascending capacity scan.

Before each update, dp[currentCapacity] still stores the previous-row skip value. A smaller array position already stores the current-row take remainder. Calculating current before replacing dp[currentCapacity] preserves both choices in the required order.

Algorithm

• Create a one-dimensional dp array of size capacity + 1, because only one value per capacity remains necessary during a row update.

• Fill dp with unlimited copies of item 0, preserving the tabulation base row before later item types are introduced.

• Process item indices from 1 through n - 1, so each pass transforms the previous logical row into the current logical row.

• Scan capacities in increasing order, allowing dp[currentCapacity - weights[index]] to contain the updated current-row remainder.

• Read dp[currentCapacity] before replacement as the skip value, because the old entry still represents the previous row.

• Calculate current as the larger skip or valid take value, preserving both choices before any state replacement occurs.

• Store current back into dp[currentCapacity] so the logical row advances safely, then return dp[capacity] as the full-capacity optimum.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N × capacity), where N is the number of piece lengths, because each piece length processes every capacity once with constant work per state.

Space Complexity: O(capacity), because a single dp array stores the best value for each capacity, with previous logical rows overwritten.