Solving Unbounded Knapsack Problem with Dynamic Programming

1. Introduction and Core Concepts

The unbounded knapsack problem is one of the most fundamental optimization problems in dynamic programming and combinatorial optimization. Given a set of items each with a weight and a value, and a knapsack with a maximum weight capacity W, the goal is to determine the maximum total value that can be achieved by selecting items such that the total weight does not exceed W. The key distinction of the unbounded variant is that each item type can be selected an unlimited number of times, unlike the 0/1 knapsack where each item can be used at most once.

This seemingly small difference fundamentally changes the structure of the optimal solution and the dynamic programming recurrence. In the unbounded knapsack problem, the decision is not whether to include an item, but how many copies of each item to include. This makes it a classic example of an integer linear programming problem with a single constraint, and it serves as a foundation for understanding more complex resource allocation problems. The problem is NP-hard in general when capacity is large, but it admits a pseudo-polynomial time solution using dynamic programming when capacity is reasonably bounded.

Why does the unbounded knapsack problem matter? It models countless real-world scenarios where resources are divisible into identical units and can be reused. From cutting raw materials into pieces to allocating server resources, from making change with coins to scheduling jobs, the ability to reuse items captures the essence of many industrial and computational challenges. Mastering its dynamic programming solution provides deep insight into optimal substructure, overlapping subproblems, and state transition design that applies across the entire dynamic programming category.

The Core Properties

To formalize the unbounded knapsack problem, we are given n item types, where item i has weight w[i] and value v[i], and a capacity W. We need to find non-negative integers x[i] representing the count of item i that maximize sum(v[i] * x[i]) subject to sum(w[i] * x[i]) <= W. The optimal substructure property holds: an optimal solution for capacity W contains optimal solutions for smaller capacities. If the last item added to an optimal knapsack for capacity W is of type k, then the remaining capacity W - w[k] must be filled optimally.

Unlike the 0/1 knapsack, the unbounded version exhibits a simpler state dependency that allows for significant space optimization. Because items can be reused, the order of consideration does not matter in the same way, and a one-dimensional DP array is sufficient. This property also means the problem can be viewed as a shortest or longest path problem in a directed acyclic graph where nodes represent capacities and edges represent adding an item. Understanding this graph perspective helps in visualizing why dynamic programming works and how the recurrence explores all feasible combinations efficiently without explicit enumeration.

2. How It Works

The dynamic programming approach to the unbounded knapsack problem builds solutions bottom-up by solving for all capacities from 0 to W. We define dp[w] as the maximum value achievable with capacity exactly w or at most w depending on formulation. The most common definition is dp[w] = maximum value achievable with capacity w. The base case is dp[0] = 0, representing that zero capacity yields zero value. For every other capacity, we consider all items that could fit as the last item added.

The recurrence relation is the heart of the solution. For each capacity w from 1 to W, we iterate over all item types i and consider the candidate value if we include one more copy of item i: candidate = dp[w - w[i]] + v[i] provided w[i] <= w. The optimal value for dp[w] is the maximum over all such candidates, or dp[w-1] if we allow unused capacity. More formally: dp[w] = max(dp[w], dp[w - w[i]] + v[i]) for all i where w[i] <= w. This recurrence captures the unbounded nature because dp[w - w[i]] itself may already contain copies of item i, allowing unlimited reuse.

The order of iteration is critical and is what differentiates the unbounded solution from the 0/1 solution. In the unbounded knapsack problem, we iterate over capacities in increasing order and for each capacity iterate over items, or equivalently iterate over items outer loop and capacities inner loop in increasing order. This increasing inner loop allows an item to be reused multiple times within the same outer iteration, as dp[w - w[i]] may have been updated in the current item iteration. In contrast, the 0/1 knapsack requires iterating capacities in decreasing order to prevent reuse. This subtle loop ordering is a frequent source of bugs and a key interview insight.

Optimal Substructure and Overlapping Subproblems

The unbounded knapsack problem exhibits both properties required for dynamic programming. Optimal substructure means the optimal solution for capacity w can be constructed from optimal solutions for smaller capacities. If we know the best value for every capacity less than w, we can compute the best value for w by trying each item as the final addition. Overlapping subproblems occur because many different capacities will depend on the same smaller subproblems. For example, both dp[10] and dp[11] might depend on dp[7] if an item has weight 3 or 4. A naive recursive solution would recompute dp[7] exponentially many times, while DP memoizes it once.

Conceptually, you can think of the DP table as filling a one-dimensional array where each entry represents the best achievable value up to that weight. The algorithm systematically explores the state space, ensuring that when we compute dp[w], all values dp[0...w-1] are already known and optimal. This eliminates the need for backtracking and guarantees that the final answer dp[W] is globally optimal. The transition is purely local, depending only on previously computed states and the item set, which makes the algorithm both elegant and efficient.

3. Implementation

Implementing the unbounded knapsack problem in Python is straightforward once the recurrence is understood. The most practical implementation uses a bottom-up, one-dimensional DP array for optimal space efficiency. Below are several canonical implementations that cover different approaches and use cases, from the classic iterative solution to top-down memoization and solution reconstruction.

The bottom-up approach is preferred for its iterative nature, cache friendliness, and avoidance of recursion depth limits. It runs in O(n*W) time and O(W) space, where n is the number of item types and W is the capacity. The space-optimized version is identical to the standard version for the unbounded case, as only a 1D array is needed from the start. This is a significant advantage over the 0/1 knapsack which conceptually requires a 2D table.

Bottom-Up One-Dimensional DP

# Bottom-up DP for unbounded knapsack problem - O(n*W) time, O(W) space
def unbounded_knapsack_bottom_up(values, weights, capacity):
    """
    Returns maximum value achievable with unlimited copies of each item.
    values: list of item values
    weights: list of item weights
    capacity: maximum weight capacity of knapsack
    """
    n = len(values)
    # dp[w] stores max value achievable with capacity w
    dp = [0] * (capacity + 1)

    # Build table for all capacities from 1 to W
    for w in range(1, capacity + 1):
        for i in range(n):
            # If item i fits in current capacity
            if weights[i] <= w:
                candidate = dp[w - weights[i]] + values[i]
                if candidate > dp[w]:
                    dp[w] = candidate
    return dp[capacity]

# Alternative loop order: items outer, capacity inner (also correct for unbounded)
def unbounded_knapsack_items_outer(values, weights, capacity):
    dp = [0] * (capacity + 1)
    n = len(values)
    for i in range(n):
        # Iterate capacity in INCREASING order to allow reuse
        for w in range(weights[i], capacity + 1):
            if dp[w - weights[i]] + values[i] > dp[w]:
                dp[w] = dp[w - weights[i]] + values[i]
    return dp[capacity]

# Example usage
values = [10, 30, 20]
weights = [5, 10, 15]
capacity = 100
print(unbounded_knapsack_bottom_up(values, weights, capacity))  # Expected: 300

Top-Down Memoization (Recursive with Caching)

from functools import lru_cache

def unbounded_knapsack_top_down(values, weights, capacity):
    """
    Top-down recursive solution with memoization.
    Useful for understanding recurrence and for sparse capacities.
    """
    n = len(values)

    @lru_cache(maxsize=None)
    def solve(remaining):
        # Base case: no capacity left
        if remaining == 0:
            return 0
        best = 0
        for i in range(n):
            if weights[i] <= remaining:
                # Try taking item i and solve for remaining - weights[i]
                # Note: we can reuse same item, so we call solve(remaining - weights[i])
                candidate = solve(remaining - weights[i]) + values[i]
                if candidate > best:
                    best = candidate
        return best

    return solve(capacity)

# With explicit memo dict (without lru_cache)
def unbounded_knapsack_memo(values, weights, capacity):
    memo = {}

    def helper(w):
        if w in memo:
            return memo[w]
        if w == 0:
            return 0
        best = 0
        for i in range(len(values)):
            if weights[i] <= w:
                val = helper(w - weights[i]) + values[i]
                if val > best:
                    best = val
        memo[w] = best
        return best

    return helper(capacity)

Reconstructing the Solution - Which Items Were Chosen

def unbounded_knapsack_with_reconstruction(values, weights, capacity):
    """
    Returns (max_value, item_counts) where item_counts[i] is number of copies of item i.
    """
    n = len(values)
    dp = [0] * (capacity + 1)
    # choice[w] stores the last item index used to achieve dp[w]
    choice = [-1] * (capacity + 1)

    for w in range(1, capacity + 1):
        for i in range(n):
            if weights[i] <= w:
                candidate = dp[w - weights[i]] + values[i]
                if candidate > dp[w]:
                    dp[w] = candidate
                    choice[w] = i

    # Reconstruct counts by backtracking
    counts = [0] * n
    w = capacity
    while w > 0 and choice[w] != -1:
        item = choice[w]
        counts[item] += 1
        w -= weights[item]

    return dp[capacity], counts

# Example: values [60, 100, 120], weights [10, 20, 30], capacity 50
# Optimal is 5 copies of item 0 (weight 10, value 60) = 300, or other combos
vals = [60, 100, 120]
wts = [10, 20, 30]
cap = 50
max_val, counts = unbounded_knapsack_with_reconstruction(vals, wts, cap)
print(f"Max value: {max_val}, Counts: {counts}")

Handling Large Capacities and Value Optimization

def unbounded_knapsack_optimized(values, weights, capacity):
    """
    Optimized version with early pruning and handling of zero-weight edge case.
    Also demonstrates how to handle capacities where exact fill is required.
    """
    n = len(values)
    # Filter out items with zero weight and zero value to avoid infinite loops
    filtered = [(v, w) for v, w in zip(values, weights) if not (w == 0 and v == 0)]
    # If any item has zero weight and positive value, value is unbounded (infinite)
    for v, w in filtered:
        if w == 0 and v > 0:
            return float('inf')

    values, weights = zip(*filtered) if filtered else ([], [])
    n = len(values)
    if n == 0 or capacity == 0:
        return 0

    dp = [0] * (capacity + 1)
    for w in range(1, capacity + 1):
        best = dp[w-1]  # Allow not filling completely (at most w)
        # Alternative for exact fill: best = 0 if w==0 else -1 (impossible)
        for i in range(n):
            if weights[i] <= w:
                cand = dp[w - weights[i]] + values[i]
                if cand > best:
                    best = cand
        dp[w] = best
    return dp[capacity]

def unbounded_knapsack_exact_fill(values, weights, capacity):
    """
    Variant where knapsack must be filled exactly to weight W.
    Returns -1 if exact fill is impossible.
    """
    dp = [-1] * (capacity + 1)
    dp[0] = 0
    for w in range(1, capacity + 1):
        for i in range(len(values)):
            if weights[i] <= w and dp[w - weights[i]] != -1:
                cand = dp[w - weights[i]] + values[i]
                if cand > dp[w]:
                    dp[w] = cand
    return dp[capacity]

4. Step-by-Step Example

To solidify understanding, let us walk through a concrete example of the unbounded knapsack problem. Suppose we have three item types: Item A has weight 2 and value 10, Item B has weight 3 and value 20, and Item C has weight 5 and value 30. The knapsack capacity is W = 8. We can use any number of copies of each item. What is the maximum value we can achieve?

We initialize dp[0] = 0 and create an array dp[0...8] initially all zeros. We will compute dp[w] for w = 1 to 8. For each w, we try every item that fits. At w = 1, no item fits, so dp[1] = 0. At w = 2, only Item A fits: candidate = dp[0] + 10 = 10, so dp[2] = 10. At w = 3, Item A gives dp[1] + 10 = 10, Item B gives dp[0] + 20 = 20, so dp[3] = 20.

Continuing, at w = 4: Item A gives dp[2] + 10 = 20, Item B gives dp[1] + 20 = 20, so dp[4] = 20. This corresponds to two copies of A or one copy of A plus wasted space. At w = 5: Item A gives dp[3] + 10 = 30, Item B gives dp[2] + 20 = 30, Item C gives dp[0] + 30 = 30, so dp[5] = 30. At w = 6: Item A gives dp[4] + 10 = 30, Item B gives dp[3] + 20 = 40, Item C gives dp[1] + 30 = 30, so dp[6] = 40 (two copies of B). At w = 7: Item A gives dp[5] + 10 = 40, Item B gives dp[4] + 20 = 40, Item C gives dp[2] + 30 = 40, so dp[7] = 40. Finally at w = 8: Item A gives dp[6] + 10 = 50, Item B gives dp[5] + 20 = 50, Item C gives dp[3] + 30 = 50, so dp[8] = 50.

Tracing the Optimal Selection

The final answer for capacity 8 is 50. But which items achieve this? Using the reconstruction technique, we can backtrack. Suppose we stored choice[w] as the item that gave the optimum for w. For w = 8, any of the three items leads to 50. If we pick Item A as the last item, we go to w = 6 where Item B was optimal, then to w = 3 where Item B was optimal, then to w = 0. This yields one A and two B's: weight 2 + 3 + 3 = 8, value 10 + 20 + 20 = 50. Another optimal solution is one C and one B: weight 5 + 3 = 8, value 30 + 20 = 50. Both are valid and demonstrate that multiple optimal solutions may exist.

This walkthrough reveals the power of overlapping subproblems. Notice how dp[3] was used to compute both dp[5] and dp[8], and dp[6] depended on dp[3]. Without memoization, a recursive solution would recompute these values repeatedly, leading to exponential time. The DP table ensures each subproblem is solved exactly once. Visualizing the table as a row where each cell builds upon previous cells helps to understand why the increasing capacity loop is essential for the unbounded case.

An important nuance is whether we require the knapsack to be filled exactly or at most to capacity. Our formulation allows at most W, meaning dp[w] is non-decreasing. If exact fill is required, we would initialize dp with negative infinity except dp[0] = 0 and only update when dp[w - w[i]] is reachable. For our example, exact fill happens to be possible for all even capacities and capacities 3,5,6,8, but not for 1 and 7 if we required exact fill with different items. Understanding this distinction is crucial for correctly modeling the problem.

5. Complexity Analysis

Analyzing the complexity of the unbounded knapsack problem is essential for determining its feasibility for large inputs. The classic dynamic programming solution has a pseudo-polynomial time complexity, meaning it is polynomial in the numeric value of the capacity but exponential in the number of bits needed to represent the capacity. This distinction is critical when dealing with very large capacities.

The time complexity of the bottom-up DP is O(n * W), where n is the number of item types and W is the capacity. This arises from the nested loops: outer loop over W capacities and inner loop over n items. Each state transition is O(1), so total work is proportional to the number of states times transitions per state. The space complexity is O(W) for the one-dimensional DP array, plus O(W) additional if we store choice information for reconstruction. The top-down memoization approach has the same asymptotic complexity but may have higher constant factors due to recursion overhead and potentially explores fewer states if not all capacities are reachable.

Best, average, and worst cases are largely the same for the bottom-up approach because it always iterates over all capacities and items regardless of input values. However, optimizations like early pruning, sorting items by value density, or using branch-and-bound can improve average-case performance. For sparse or large W where n * W is too large, alternative approaches like meet-in-the-middle or using integer linear programming solvers may be more appropriate, though they sacrifice the guarantee of polynomial time in W.

The table highlights that while the DP approaches share the same asymptotic bounds, the naive recursive solution is exponentially slower and should never be used beyond tiny capacities. The bottom-up method is generally preferred for its predictable performance and low overhead. When W is up to 10^4 or 10^5 and n is moderate, the O(n*W) solution is highly practical. When W reaches 10^9, however, the pseudo-polynomial nature becomes prohibitive, and you must consider alternative formulations such as greedy approximations for specific value structures or using the concept of unbounded knapsack with monotone queue optimization which can reduce time to O(n*W) with better constants or even O(n log W) for certain cases.

Space-Time Tradeoffs

The O(W) space usage is optimal for the value-only problem, but reconstructing the solution requires additional O(W) for the choice array. If memory is extremely constrained, you can reconstruct by re-running the DP backwards from W without storing choices, at the cost of O(n) extra time per step. Another optimization is to use a short integer type if values fit, or to use Python's array module for large W. For very large W where O(W) memory is impossible, you can use a divide-and-conquer DP optimization or consider that if weights are small, the solution becomes periodic after a certain capacity due to the Chicken McNugget theorem, allowing O(n * max(w)) time.

6. Variations and Optimizations

The classic unbounded knapsack problem has numerous variations and optimization opportunities that extend its applicability. Understanding these variants helps in recognizing when a problem is a disguised knapsack and how to adapt the core DP to new constraints.

One common variation is the coin change problem, which is essentially an unbounded knapsack where the goal is to count the number of ways to make change or to find the minimum number of coins to reach a target amount. The recurrence changes slightly: for counting ways, dp[w] += dp[w - coin] and loop order matters to avoid counting permutations as distinct. For minimum coins, dp[w] = min(dp[w], dp[w - coin] + 1). Another variation is the rod cutting problem, where a rod of length W can be cut into pieces of different lengths with different prices, and each piece length can be used unlimited times. This is exactly the unbounded knapsack with weight = length and value = price.

Optimization techniques can significantly improve performance. The monotone queue optimization can reduce the time complexity when weights are small or when the DP transition has convexity properties. For the general case, a simple but effective optimization is to remove dominated items: if item i has weight greater than or equal to item j but value less than or equal to item j, then item i is never useful and can be discarded. Sorting items by weight or by value density (value per weight) can also enable early pruning. Additionally, if the capacity is huge but the number of item types is small, you can use the concept of the optimal value density item to fill the remaining capacity greedily after a certain bound, leveraging number theory results about the Frobenius number.

Advanced Variants

The bounded knapsack, where each item has a limited quantity, can be reduced to the unbounded case via binary splitting or monotone queue techniques. The 0/1 knapsack is a special case of bounded with quantity 1. The fractional knapsack, where items can be divided, is not solved by DP but by a greedy algorithm sorting by value density, and it provides an upper bound for the integer versions. The multidimensional knapsack adds multiple constraints such as weight and volume, requiring a 2D or higher DP table and increasing complexity to O(n * W * V).

Another interesting optimization is using bitset or boolean DP for the decision version where we only care about reachability, not maximum value. This can be accelerated using bitset operations where each bit represents reachable capacity, and shifting the bitset by w[i] corresponds to adding item i. With Python's integers as bitsets or using the bitarray library, this can be extremely fast for large W when values are uniform. For value maximization, you can also use branch and bound with linear programming relaxation to prune search space in a hybrid DP-search approach.

When values and weights are large, consider scaling techniques or fully polynomial-time approximation schemes (FPTAS) that trade a small epsilon of optimality for polynomial time in n and 1/epsilon rather than W. These are crucial for production systems where W might be on the order of millions and exact DP is infeasible.

7. Real-World Applications

The unbounded knapsack problem is far from a purely academic exercise; it underpins many practical systems in computing and industry. Its ability to model unlimited reuse of resources makes it a natural fit for allocation and cutting problems.

In operating systems and cloud infrastructure, resource allocation often maps to an unbounded knapsack. Consider a web server that can spawn multiple instances of different microservices, each requiring a certain amount of RAM and CPU and providing a certain throughput value. Given a fixed server capacity, which combination of service instances maximizes total throughput? This is an unbounded knapsack where item types are service types. Similarly, container scheduling in Kubernetes, where pods of the same deployment can be replicated unlimited times subject to node capacity, is a multidimensional unbounded knapsack.

In finance and manufacturing, the cutting stock problem is a classic application. A factory has rolls of raw material of length W and needs to cut them into pieces of various lengths to fulfill orders, each piece length having a profit value. The goal is to maximize profit per roll by choosing how many pieces of each length to cut. This directly corresponds to the unbounded knapsack. The same model applies to cargo loading where a shipping container can be filled with unlimited copies of different box types, or to budget allocation where a marketing budget can be spent on multiple campaigns of the same type.

In networking, bandwidth allocation for video streaming services can be modeled as an unbounded knapsack where each stream type requires a certain bandwidth and provides a certain user satisfaction score. The network link has a total bandwidth capacity, and the provider can allocate any number of streams of each quality level. In databases, the buffer pool can cache multiple copies of different page types or allocate memory to different query operators, each with a memory cost and performance benefit, to maximize overall query throughput.

Even in everyday software, the unbounded knapsack appears in spell checkers and text formatting where line breaking with unlimited word usage patterns is optimized, and in game development for inventory systems where players can carry unlimited copies of stackable items. Recognizing these mappings allows engineers to apply a well-understood DP solution rather than reinventing a custom heuristic.

8. Comparison with Alternatives

Choosing the right knapsack variant and solution technique is crucial. The unbounded knapsack problem is often confused with its close relatives, and understanding their differences prevents modeling errors and inefficient solutions.

The 0/1 knapsack allows each item to be used at most once, making it suitable for unique items like selecting projects or choosing which files to back up. Its DP requires a 2D table or a 1D table iterated in reverse to prevent reuse, and it has the same O(n*W) time but is conceptually slightly more complex. The fractional knapsack allows items to be divided arbitrarily and is solved optimally by a greedy algorithm in O(n log n) time, making it much faster but applicable only when divisibility is allowed, such as allocating continuous resources like water or time. The bounded knapsack generalizes both by allowing a limited number of copies per item, requiring more complex handling via binary optimization or monotone queues.

For the unbounded case itself, alternative solution approaches include greedy by value density, which is fast but not optimal except for special cases like canonical coin systems, and branch-and-bound search, which can be faster for very large W with pruning but has exponential worst-case time. Integer linear programming solvers can handle additional constraints but are overkill for the pure knapsack. The DP approach remains the gold standard for exact solutions with moderate W due to its guarantee of optimality and predictable performance.

The table makes it clear that the choice depends on the problem's reuse constraint and whether divisibility is allowed. A common mistake is to apply the 0/1 DP to an unbounded problem by mistake, which will undercount the optimum by not allowing reuse, or to apply the unbounded DP to a 0/1 problem, which will overcount by illegally reusing items. Always verify the problem statement: phrases like "unlimited supply," "any number of copies," or "with replacement" indicate the unbounded variant, while "each item can be chosen at most once" indicates 0/1.

From a performance perspective, if W is extremely large, none of the pseudo-polynomial DP solutions may be feasible, and you may need to consider approximation algorithms or use the fact that the unbounded knapsack has a fully polynomial-time approximation scheme. For small n and large W, techniques based on the concept of the best density item and residue classes modulo the smallest weight can solve the problem in O(n * min(w)) time, which is independent of W.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing the unbounded knapsack problem. Awareness of these pitfalls and adherence to best practices ensures correctness and efficiency.

The most frequent mistake is incorrect loop order. Using a decreasing inner loop for capacities, as required for 0/1 knapsack, will incorrectly prevent item reuse and yield a suboptimal answer for the unbounded case. Always iterate capacities in increasing order when items are in the outer loop, or iterate items inside the capacity loop. A second common error is mishandling the base case and initialization. Initializing dp with zeros works for the "at most W" variant, but for the "exactly W" variant you must initialize with negative infinity except dp[0] = 0 to mark unreachable states. Failing to do so can return a value for an impossible exact fill.

Another pitfall is integer overflow or infinite loops with zero-weight items. If an item has weight zero and positive value, the optimal value is infinite, and the DP will loop forever or overflow. Always check for and handle zero-weight items explicitly. Similarly, not considering that dp[w] should be at least dp[w-1] for the at-most variant can lead to non-monotonic results if you forget to carry over the best value for unused capacity. In Python, using recursion without memoization or without increasing recursion limits can cause stack overflows for large W.

Best Practices

• Clarify the variant first: Determine whether the problem allows unlimited reuse, requires exact fill, or allows at most capacity. Write the recurrence explicitly before coding.
• Use iterative bottom-up as default: It avoids recursion depth issues, is faster in Python due to loop overhead, and makes reconstruction easier. Reserve top-down for sparse or very large W where many states are unreachable.
• Validate inputs: Check for zero or negative weights and values, empty item lists, and capacity zero. Filter dominated items to reduce n and improve speed.
• Test with small brute force: For small W and n, write a brute-force enumerator to verify DP results on random tests. This catches loop-order bugs quickly.
• Document loop order: Add a comment explaining why the inner loop is increasing for unbounded. This prevents future maintainers from "fixing" it to decreasing.
• Consider Python specifics: Use local variables for speed inside loops, consider using array('l') or list of ints, and avoid heavy object overhead. For very large W, use PyPy or Numba for acceleration.

Performance best practices include pre-sorting items and removing dominated ones, using early termination if dp[W] stops improving, and for large W considering the optimized residue class method. Always profile with realistic data sizes: an O(n*W) solution with W = 10^6 and n = 100 requires 100 million iterations, which may be borderline in Python and might require PyPy, Numba, or a switch to a more optimized language or approximation.

Finally, ensure you escape HTML special characters if displaying code on the web, and include comprehensive comments in your implementation. The unbounded knapsack problem is a staple in code reviews and interviews, so clarity and correctness of the DP transition are more important than micro-optimizations. Write code that clearly shows dp[w - weights[i]] + values[i] and the max operation, and include docstrings that state time and space complexity.

10. Interview Questions

The unbounded knapsack problem is a favorite in technical interviews because it tests understanding of dynamic programming fundamentals, loop ordering, and problem modeling. Below are common interview questions and how to approach them effectively.

Question 1: Explain the difference between 0/1 and unbounded knapsack and how the code differs.

Answer approach: State that 0/1 allows each item once, unbounded allows unlimited copies. The DP recurrence is similar but the implementation differs in loop order. For unbounded, iterate capacity in increasing order so that dp[w - w[i]] already includes the possibility of using item i again. For 0/1, iterate capacity in decreasing order to ensure each item is used at most once per iteration. Provide both code snippets and emphasize that swapping the loop order is the critical bug to avoid. Mention space: both can be O(W) but 0/1 conceptually needs 2D.

Question 2: Given coin denominations [1,3,4] and amount 6, find the minimum number of coins to make change. How is this an unbounded knapsack?

Answer approach: Map coin denomination to weight and value to 1 per coin, but minimize count instead of maximize value. The DP is dp[w] = min(dp[w], dp[w - coin] + 1) with dp[0] = 0 and others initialized to infinity. Walk through W=6: optimal is two 3's = 2 coins, not 3+1+1+1 or 4+1+1. Explain that this is unbounded because unlimited coins of each denomination are available. Discuss why greedy fails: for [1,3,4], greedy for 6 would pick 4+1+1 = 3 coins, not optimal. This demonstrates that greedy by largest denomination is not always optimal for arbitrary coin systems.

Question 3: How would you reconstruct the actual items chosen, not just the max value?

Answer approach: Describe storing a choice array where choice[w] records which item was last used to achieve dp[w]. After filling dp, backtrack from W by repeatedly subtracting weights[choice[w]] and incrementing counts. Provide the reconstruction code and note that multiple optimal solutions may exist, so any valid reconstruction is acceptable. Mention alternative without extra storage: re-derive choices by re-checking which item satisfies dp[w] == dp[w - w[i]] + v[i] during backtracking, trading time for space.

Question 4: What if capacity W is up to 10^9? Can you still use DP?

Answer approach: Explain that O(n*W) DP is infeasible for W=10^9 due to pseudo-polynomial complexity. Discuss alternatives: if weights are small, use the residue class optimization that runs in O(n * max(w)) by exploiting periodicity; if values are small, consider DP on value instead of weight; otherwise use approximation algorithms or branch-and-bound. Mention that if one item has the best value density, after a certain bound (Frobenius number) the solution becomes greedy with that item. This shows understanding of scalability and limitations of DP.

Question 5: Solve the rod cutting problem: rod length 8, prices for lengths 1..8 are [1,5,8,9,10,17,17,20]. What is the max revenue?

Answer approach: Recognize rod cutting as unbounded knapsack where weight = length, value = price, capacity = rod length. Apply DP: dp[l] = max(dp[l], dp[l - len] + price[len]). Compute: dp[1]=1, dp[2]=5, dp[3]=8, dp[4]=10 (2+2), dp[5]=13, dp[6]=17, dp[7]=18, dp[8]=22 (2+6). Explain that cutting into 2+6 yields 5+17=22 which is better than not cutting (20). Emphasize that unlimited cuts of each length are allowed, hence unbounded. Provide code and note that this is exactly the unbounded knapsack with n=W item types.

Preparing for these questions involves not just memorizing code but understanding the underlying principles, being able to derive the recurrence on the spot, and discussing tradeoffs. Practice implementing both loop orders, handling edge cases, and explaining the time and space complexity clearly. Interviewers often follow up by asking to modify the problem to bounded or exact-fill variants, so be ready to adapt the DP initialization and transition accordingly.