Unbounded Knapsack

1. 1.Unbounded Knapsack
   1D DP left-to-right loop: dp[w] = max(dp[w], val + dp[w-wt])medium
2. 2.Coin Change
   Unbounded min coins DP: dp[a] = min(dp[a], 1 + dp[a-coin])medium
3. 3.Coin Change II
   Unbounded combinations: outer coin loop, inner amount left-to-rightmedium
4. 4.Rod Cutting
   Unbounded Knapsack mapping: piece length = weight, selling price = valuemedium
5. 5.Combination Sum IV
   Unbounded permutations: outer amount loop, inner coin loopmedium
6. 6.Perfect Squares
   Unbounded min items DP: dp[i] = min(dp[i], 1 + dp[i - s*s])medium
7. 7.Minimum Cost to Fill Given Weight
   Unbounded min cost DP with exact weight capacity targetmedium
8. 8.Integer Break
   Unbounded product maximization DP for integer split partsmedium
9. 9.Minimum Coins to Make Amount
   Unbounded DP initialized with INF for unreachable amountsmedium
10. 10.Count Ways to Make Amount
    Unbounded combination counting with outer coin loopmedium
11. 11.Maximum Value With Unlimited Items
    Unbounded max value DP with forward capacity updatingmedium
12. 12.Cutting Rod for Maximum Profit
    Rod cutting DP with length-to-price array evaluationmedium
13. 13.Number of Ways to Reach Target With Reusable Values
    Unbounded combination counting DPmedium
14. 14.Complete Knapsack
    Synonym for Unbounded Knapsack (unlimited item reuse)medium
15. 15.Unlimited Supply Knapsack
    Base Unbounded Knapsack 1D forward capacity updatingmedium

1. 16.Coin Change With Limited/Unlimited Comparison
   0/1 backwards capacity loop vs Unbounded forwards capacity loop comparisonmedium
2. 17.Minimum Cost With Reusable Choices
   Unbounded min cost transition across reusable item choicesmedium
3. 18.Count Ordered Combinations
   Unbounded permutation counting with outer target loopmedium
4. 19.Knapsack With Exact Fill
   Exact capacity fill using INF / -INF base initializationsmedium
5. 20.Multi-Dimensional Unbounded Knapsack — advanced
   Multiple capacity dimensions (e.g. weight + volume) updated forwardshard

1. Can I reuse the same item unlimited times?Unbounded Knapsack
2. Unlimited coins or rod pieces?Unbounded Knapsack
3. Using 1D DP array?Capacity loop LEFT -> RIGHT (Forwards)
4. Why forward loop?dp[w] reads NEWLY updated dp[w-wt] of current item
5. TAKE recursive transition?solve(i, cap - wt) (index stays on SAME item i)

package main

import "fmt"

// Unbounded Knapsack 2D Matrix DP: Reads SAME ROW dp[i] on TAKE
func unboundedKnapsack2D(weights []int, values []int, capacity int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }

    for i := 1; i <= n; i++ {
        wt, val := weights[i-1], values[i-1]
        for w := 0; w <= capacity; w++ {
            dp[i][w] = dp[i-1][w] // SKIP item i
            if wt <= w {
                take := val + dp[i][w-wt] // TAKE item i (reads SAME ROW i!)
                if take > dp[i][w] {
                    dp[i][w] = take
                }
            }
        }
    }
    return dp[n][capacity]
}

// Unbounded Knapsack Space-Optimized 1D DP: O(W) space
func unboundedKnapsack1D(weights []int, values []int, capacity int) int {
    dp := make([]int, capacity+1)
    for i := 0; i < len(weights); i++ {
        wt, val := weights[i], values[i]
        // LEFT-TO-RIGHT LOOP: enables reusing current item i multiple times!
        for w := wt; w <= capacity; w++ {
            if val+dp[w-wt] > dp[w] {
                dp[w] = val + dp[w-wt]
            }
        }
    }
    return dp[capacity]
}

func main() {
    weights := []int{2, 3, 4}
    values := []int{5, 8, 11}
    cap := 6

    fmt.Println("2D Max Value:", unboundedKnapsack2D(weights, values, cap)) // Output: 16 (Items 3+3)
    fmt.Println("1D Max Value:", unboundedKnapsack1D(weights, values, cap)) // Output: 16
}

Core Unbounded Mechanics & Golden Difference

Unbounded Definition -> Item CAN BE REUSED UNLIMITED TIMES
Recursive TAKE -> solve(i, cap - wt) (Stay on SAME item i)
2D Matrix -> dp[i][w] = max(dp[i-1][w], val + dp[i][w-wt]) (Reads SAME ROW i)
1D Array -> Loop capacity w = wt up to W (Left-to-Right / Forwards)
Rod Cutting -> Capacity = Rod Length, Item Weight = Piece Length, Item Value = Price
Coin Change II -> Outer coin loop (Combinations Count)
Combination Sum IV -> Outer amount loop (Permutations Count)

Unbounded Variants & Exact Fill Initializations

Common Interview Mistakes

• • Iterating 1D capacity loop backwards (Right-to-Left), accidentally enforcing 0/1 single item use.
• • Reading previous row dp[i-1][w-wt] in 2D TAKE transition instead of same row dp[i][w-wt].
• • Advancing item index i -> i+1 in recursive TAKE choice (solve(i+1, cap-wt)), preventing item reuse.
• • Swapping loop order in Coin Change II (accidentally counting permutations instead of combinations).
• • Using 0 base initialization for minimum exact fill problems instead of infinity (INF).
• • Confusing Coin Change (min coins DP) with Coin Change II (combinations count DP).
• • Assuming item weight = 0 can be handled safely without checking for infinite value recursion loops.
• • Attempting 1D capacity DP when target W = 10^9 without checking constraint bounds (Memory Limit Exceeded).
• • Assuming unlimited item supply means infinite answer (capacity W still bounds maximum usable copies).

Interview Rules

Reusable item supply + capacity limit? → Unbounded Knapsack DP
Rule 1                                  → Define dp[w] state meaning explicitly
Rule 2                                  → Recursive TAKE stays on same item: solve(i, cap - wt)
Rule 3                                  → 2D Matrix TAKE reads SAME ROW: dp[i][w-wt]
Rule 4                                  → 1D Array: Loop capacity w = wt up to W (Left-to-Right / Forwards)
Rule 5                                  → Coin Change II = Outer coin loop; Combination Sum IV = Outer amount loop
Rule 6                                  → Rod Cutting = Unbounded Knapsack with piece length = weight
Time Complexity                         → O(N * Capacity) (Pseudo-Polynomial)
Space Complexity                        → O(N * Capacity) 2D Table or O(Capacity) 1D Array

💡 Golden Rule: If an item can be used again after taking it, keep that item available and update capacity forward so the current iteration may reuse its newly computed states.

Unbounded Rule: Item reusable UNLIMITED times
Recursive TAKE: solve(i, cap - wt) (Stay on index i)
1D Array: Loop Capacity LEFT-TO-RIGHT (w = wt up to W)
2D Matrix: TAKE reads Same Row dp[i][w-wt]
Rod Cutting: Capacity = Rod Length, Weight = Piece Length, Value = Price
Coin Change: Min coins DP (dp[0]=0, others INF)
Coin Change II: Combinations count (Outer coin loop)