Pattern 3: Bounded Knapsack (Resource Allocation) Problems

The Resource Management Pattern: Make choices for items under a constraint (capacity/budget/target). State tracks items processed and resource remaining.

---

The Core Pattern

THE MENTAL MODEL

Imagine you have a backpack with limited capacity and items to choose from:

1. For each item, you decide: take it or leave it
2. Taking it consumes resources (weight, space, budget)
3. You want to optimize some value (maximize profit, minimize cost, count ways)
4. You track: which items you've considered + how much resource remains

This is Bounded Knapsack DP.

Pattern Recognition

WHEN YOU SEE THIS PATTERN

Keywords: "capacity", "budget", "target sum", "select items", "weight limit", "subset", "coins"

Structure:

• Collection of items to choose from
• Limited resource (weight, capacity, sum, count)
• Each item has a cost and/or value
• Goal: optimize or count under constraint

State: dp[i][resource] = "best answer using first i items with resource constraint"

Transition: For each item, try:

• Skip it: dp[i-1][resource]
• Take it: dp[i-1][resource - cost] + value (if cost ≤ resource)

---

Category 1: Core Knapsack Problems

1. 0/1 Knapsack (Classic)

PROBLEM

Given n items where each item has:

• weight[i] = weight of item i
• value[i] = value of item i

And a knapsack with capacity W, find the maximum value you can carry.

Constraint: Each item can be used at most once.

State Definition: dp[i][w] = maximum value using first i items with capacity w

Transition:

dp[i][w] = Math.max(
    dp[i-1][w],                           // skip item i
    dp[i-1][w - weight[i]] + value[i]     // take item i (if fits)
);

public int knapsack(int W, int[] weights, int[] values, int n) {
    int[][] dp = new int[n + 1][W + 1];

    // Base case: dp[0][w] = 0 (no items = no value)
    // Base case: dp[i][0] = 0 (no capacity = no value)

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            // Option 1: Don't take item i
            dp[i][w] = dp[i-1][w];

            // Option 2: Take item i (if it fits)
            if (weights[i-1] <= w) {
                dp[i][w] = Math.max(
                    dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                );
            }
        }
    }

    return dp[n][W];
}

THE FOUNDATION OF KNAPSACK

This is the template for all knapsack problems:

1. 2D state: [items considered][resource remaining]
2. Binary choice: skip or take
3. Take only if resource constraint satisfied

Master this, and all variations become easy.

---

2. Partition Equal Subset Sum (LC 416)

PROBLEM

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of elements in both subsets is equal.

Example: [1,5,11,5] → true (can partition into [1,5,5] and [11])

State Definition: dp[i][sum] = true if we can make sum using first i numbers

Transition:

dp[i][sum] = dp[i-1][sum]                    // don't use nums[i]
          || dp[i-1][sum - nums[i]]          // use nums[i]

public boolean canPartition(int[] nums) {
    int totalSum = 0;
    for (int num : nums) totalSum += num;

    // If odd sum, can't partition equally
    if (totalSum % 2 != 0) return false;

    int target = totalSum / 2;
    int n = nums.length;
    boolean[][] dp = new boolean[n + 1][target + 1];

    // Base case: sum = 0 is always achievable (take nothing)
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    for (int i = 1; i <= n; i++) {
        for (int sum = 1; sum <= target; sum++) {
            // Don't take nums[i-1]
            dp[i][sum] = dp[i-1][sum];

            // Take nums[i-1] (if it doesn't exceed sum)
            if (nums[i-1] <= sum) {
                dp[i][sum] = dp[i][sum] || dp[i-1][sum - nums[i-1]];
            }
        }
    }

    return dp[n][target];
}

KNAPSACK IN DISGUISE

This is 0/1 Knapsack where:

• Items = numbers in array
• Capacity = target sum (half of total)
• Goal = can we reach exactly target? (instead of max value)

Pattern Recognition: "Can we make a sum/subset?" → Think Knapsack!

---

3. Target Sum (LC 494)

PROBLEM

You are given an integer array nums and an integer target. You want to build an expression by adding + or - before each integer in nums.

Return the number of different expressions you can build that evaluate to target.

Example: nums = [1,1,1,1,1], target = 3 → 5 ways

State Definition: dp[i][sum] = number of ways to reach sum using first i numbers

Transition:

dp[i][sum] = dp[i-1][sum - nums[i]]      // add +nums[i]
           + dp[i-1][sum + nums[i]]      // add -nums[i]

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int num : nums) sum += num;

    // Impossible cases
    if (Math.abs(target) > sum) return 0;
    if ((target + sum) % 2 != 0) return 0;

    // Transform: find subset with sum = (target + sum) / 2
    int subsetSum = (target + sum) / 2;
    int n = nums.length;
    int[][] dp = new int[n + 1][subsetSum + 1];

    dp[0][0] = 1;  // one way to make sum 0 with 0 items

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= subsetSum; j++) {
            dp[i][j] = dp[i-1][j];  // don't use nums[i-1]

            if (j >= nums[i-1]) {
                dp[i][j] += dp[i-1][j - nums[i-1]];  // use nums[i-1]
            }
        }
    }

    return dp[n][subsetSum];
}

THE CLEVER TRANSFORMATION

Math Trick:

• Let P = sum of positive numbers, N = sum of negative numbers
• P - N = target
• P + N = sum (total sum)
• Solving: P = (target + sum) / 2

Problem becomes: Find subsets with sum = (target + sum) / 2

This is Partition Problem! Counting version.

---

4. Last Stone Weight II (LC 1049)

State Definition: dp[i][diff] = true if we can achieve difference diff using first i stones

Transition: Same as partition (minimize difference between two groups)

public int lastStoneWeightII(int[] stones) {
    int sum = 0;
    for (int stone : stones) sum += stone;

    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int stone : stones) {
        for (int j = target; j >= stone; j--) {
            dp[j] = dp[j] || dp[j - stone];
        }
    }

    // Find largest achievable sum <= target
    for (int j = target; j >= 0; j--) {
        if (dp[j]) {
            return sum - 2 * j;  // difference
        }
    }

    return 0;
}

PATTERN VARIANT

Goal: Minimize the difference between two groups.

Same as partition, but instead of "equal", we find "closest to equal".

---

5. Ones and Zeroes (LC 474)

PROBLEM

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and at most n 1's in the subset.

State Definition: dp[i][m][n] = max size of subset using first i strings with at most m zeros and n ones

Transition:

dp[i][m][n] = Math.max(
    dp[i-1][m][n],                               // skip string i
    1 + dp[i-1][m - zeros[i]][n - ones[i]]      // take string i
);

public int findMaxForm(String[] strs, int m, int n) {
    int len = strs.length;
    int[][][] dp = new int[len + 1][m + 1][n + 1];

    for (int i = 1; i <= len; i++) {
        int[] count = countZeroesOnes(strs[i-1]);
        int zeros = count[0];
        int ones = count[1];

        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                // Don't take string i
                dp[i][j][k] = dp[i-1][j][k];

                // Take string i (if enough 0s and 1s)
                if (j >= zeros && k >= ones) {
                    dp[i][j][k] = Math.max(
                        dp[i][j][k],
                        1 + dp[i-1][j - zeros][k - ones]
                    );
                }
            }
        }
    }

    return dp[len][m][n];
}

private int[] countZeroesOnes(String s) {
    int[] count = new int[2];
    for (char c : s.toCharArray()) {
        count[c - '0']++;
    }
    return count;
}

3D KNAPSACK!

This is 2D knapsack (two resource constraints: zeros AND ones).

Pattern Extension: Multiple resource constraints → Multiple dimensions in state.

---

Category 2: Coin Change Variants

6. Coin Change (LC 322) - Unbounded

PROBLEM

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins needed to make up that amount. Each coin can be used unlimited times.

State Definition: dp[i][amount] = minimum coins to make amount using first i coin types

Transition (Unbounded):

dp[i][amount] = Math.min(
    dp[i-1][amount],                    // don't use coin i
    1 + dp[i][amount - coin[i]]        // use coin i (can use again!)
);

public int coinChange(int[] coins, int amount) {
    int n = coins.length;
    int[][] dp = new int[n + 1][amount + 1];

    // Base case: infinite coins needed for amount > 0 with 0 coin types
    for (int j = 1; j <= amount; j++) {
        dp[0][j] = Integer.MAX_VALUE - 1;  // -1 to avoid overflow
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++) {
            // Don't use coin i
            dp[i][j] = dp[i-1][j];

            // Use coin i (if it fits)
            if (j >= coins[i-1]) {
                dp[i][j] = Math.min(
                    dp[i][j],
                    1 + dp[i][j - coins[i-1]]  // Note: dp[i], not dp[i-1]!
                );
            }
        }
    }

    return dp[n][amount] >= Integer.MAX_VALUE - 1 ? -1 : dp[n][amount];
}

BOUNDED VS UNBOUNDED

Bounded (0/1): Each item used at most once

• Transition: dp[i-1][w - cost] (previous row)

Unbounded: Each item used unlimited times

• Transition: dp[i][w - cost] (same row)

Why same row? Because we can use the same coin multiple times!

---

7. Coin Change II (LC 518) - Unbounded

State Definition: dp[i][amount] = number of ways to make amount using first i coins

Transition (Unbounded):

dp[i][amount] = dp[i-1][amount]              // don't use coin i
              + dp[i][amount - coin[i]]      // use coin i

public int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = new int[n + 1][amount + 1];

    // Base case: 1 way to make amount 0 (use no coins)
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++) {
            dp[i][j] = dp[i-1][j];  // don't use coin i

            if (j >= coins[i-1]) {
                dp[i][j] += dp[i][j - coins[i-1]];  // use coin i
            }
        }
    }

    return dp[n][amount];
}

COUNTING VS MINIMIZING

• Coin Change: Minimize count (use min)
• Coin Change II: Count ways (use +)

Same structure, different operation!

---

8. Perfect Squares (LC 279)

State Definition: dp[n] = minimum number of perfect squares that sum to n

Transition:

dp[n] = Math.min(dp[n], 1 + dp[n - i*i]) for all i where i*i <= n

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);
        }
    }

    return dp[n];
}

UNBOUNDED KNAPSACK VARIANT

Items = perfect squares (1, 4, 9, 16, ...) Capacity = target number n Goal = minimize count

Each square can be used unlimited times!

---

9. Minimum Cost For Tickets (LC 983)

State Definition: dp[i] = minimum cost to cover all travel days up to day i

Transition: Try all ticket types (1-day, 7-day, 30-day)

public int mincostTickets(int[] days, int[] costs) {
    int lastDay = days[days.length - 1];
    boolean[] isTravelDay = new boolean[lastDay + 1];
    for (int day : days) {
        isTravelDay[day] = true;
    }

    int[] dp = new int[lastDay + 1];

    for (int i = 1; i <= lastDay; i++) {
        if (!isTravelDay[i]) {
            dp[i] = dp[i-1];  // not traveling, no cost
            continue;
        }

        // Option 1: 1-day pass
        int cost1 = dp[i-1] + costs[0];

        // Option 2: 7-day pass
        int day7 = Math.max(0, i - 7);
        int cost7 = dp[day7] + costs[1];

        // Option 3: 30-day pass
        int day30 = Math.max(0, i - 30);
        int cost30 = dp[day30] + costs[2];

        dp[i] = Math.min(cost1, Math.min(cost7, cost30));
    }

    return dp[lastDay];
}

---

10. Combination Sum IV (LC 377) - Order Matters

State Definition: dp[amount] = number of ways to make amount (order matters!)

Transition:

dp[amount] = sum(dp[amount - num]) for all num in nums where num <= amount

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;

    for (int i = 1; i <= target; i++) {
        for (int num : nums) {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }

    return dp[target];
}

ORDER MATTERS!

Coin Change II: Combinations (order doesn't matter)

• Loop coins first: for coin: for amount

Combination Sum IV: Permutations (order matters)

• Loop amount first: for amount: for nums

Different loop order → different counting!

---

Category 3: Subset Selection

11. Partition to K Equal Sum Subsets (LC 698)

State Definition: dp[mask][current_sum] = true if we can partition items indicated by mask to reach target

Transition: Include/exclude each number

BITMASK DP

When tracking "which items used", use bitmask to represent subsets.

This is advanced knapsack with subset tracking.

---

12. Tallest Billboard (LC 956)

State Definition: dp[i][diff] = maximum height when difference between two piles is diff using first i rods

Transition: Each rod can go to:

• Left pile
• Right pile
• Not used

HARD PROBLEM

This requires tracking difference between two subsets instead of just one sum.

Pattern Extension: Two knapsacks being filled simultaneously.

---

13. Shopping Offers (LC 638)

State Definition: dp[needs] = minimum cost to fulfill needs (a shopping cart)

Transition: Either buy individual items or use a special offer

---

14. Number of Dice Rolls With Target Sum (LC 1155)

State Definition: dp[i][sum] = number of ways to get sum using i dice

Transition:

dp[i][sum] = sum(dp[i-1][sum - face]) for face in 1..k

public int numRollsToTarget(int n, int k, int target) {
    int MOD = 1_000_000_007;
    int[][] dp = new int[n + 1][target + 1];
    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= target; j++) {
            for (int face = 1; face <= k; face++) {
                if (j >= face) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j - face]) % MOD;
                }
            }
        }
    }

    return dp[n][target];
}

UNBOUNDED-LIKE PATTERN

Items = dice (each can show 1 to k) Resource = target sum Count = number of dice used

Similar to coin change but counting dice instead of minimizing coins.

---

15. Profitable Schemes (LC 879)

State Definition: dp[i][n][profit] = number of ways to get at least profit with at most n people using first i crimes

Transition:

dp[i][n][profit] = dp[i-1][n][profit]
                 + dp[i-1][n - people[i]][max(0, profit - profit[i])]

---

Category 4: String/Sequence Variants

16. Minimum ASCII Delete Sum for Two Strings (LC 712)

State Definition: dp[i][j] = minimum ASCII delete sum to make first i characters of s1 equal to first j characters of s2

Transition:

if (s1[i-1] == s2[j-1]) {
    dp[i][j] = dp[i-1][j-1];  // no deletion needed
} else {
    dp[i][j] = Math.min(
        dp[i-1][j] + s1[i-1],      // delete from s1
        dp[i][j-1] + s2[j-1]       // delete from s2
    );
}

KNAPSACK ON STRINGS

This is knapsack thinking applied to string matching:

• Items = characters
• Resource = positions in both strings
• Cost = ASCII values

---

17. Form Largest Integer With Digits That Add up to Target (LC 1449)

State Definition: dp[target] = maximum number of digits achievable with cost exactly target

Transition: For each cost value, try using it

---

18. Count Ways to Build Good Strings (LC 2466)

State Definition: dp[length] = number of ways to build string of length

Transition: Add zero zeros or one ones (bounded by counts)

---

19. Maximum Value of K Coins From Piles (LC 2218)

State Definition: dp[i][k] = maximum value from first i piles taking k coins total

Transition: For pile i, try taking 0, 1, 2, ..., min(k, pile[i].length) coins

public int maxValueOfCoins(List<List<Integer>> piles, int k) {
    int n = piles.size();
    int[][] dp = new int[n + 1][k + 1];

    for (int i = 1; i <= n; i++) {
        for (int coins = 0; coins <= k; coins++) {
            int currentPileSum = 0;

            // Try taking 0, 1, 2, ..., min(coins, pile size) from pile i
            for (int take = 0; take <= Math.min(coins, piles.get(i-1).size()); take++) {
                if (take > 0) {
                    currentPileSum += piles.get(i-1).get(take - 1);
                }

                dp[i][coins] = Math.max(
                    dp[i][coins],
                    dp[i-1][coins - take] + currentPileSum
                );
            }
        }
    }

    return dp[n][k];
}

MULTIPLE ITEMS PER "PILE"

Instead of binary choice (take/skip), we have multiple choices: how many to take from this pile?

Pattern Extension: Bounded knapsack with quantity limits per item.

---

20. Minimum Difficulty of a Job Schedule (LC 1335)

State Definition: dp[i][d] = minimum difficulty for first i jobs in d days

Transition: Partition jobs—each partition's difficulty = max job difficulty in that day

public int minDifficulty(int[] jobDifficulty, int d) {
    int n = jobDifficulty.length;
    if (n < d) return -1;

    int[][] dp = new int[n][d + 1];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }

    // Base case: all jobs in day 1
    dp[0][1] = jobDifficulty[0];
    for (int i = 1; i < n; i++) {
        dp[i][1] = Math.max(dp[i-1][1], jobDifficulty[i]);
    }

    for (int day = 2; day <= d; day++) {
        for (int i = day - 1; i < n; i++) {
            // Try all possible splits
            for (int j = i; j >= day - 1; j--) {
                int maxDifficulty = 0;
                for (int k = j; k <= i; k++) {
                    maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k]);
                }

                if (dp[j-1][day-1] != Integer.MAX_VALUE) {
                    dp[i][day] = Math.min(
                        dp[i][day],
                        dp[j-1][day-1] + maxDifficulty
                    );
                }
            }
        }
    }

    return dp[n-1][d];
}

---

The Common Thread

WHAT MAKES THESE ALL THE SAME PATTERN?

Every problem has:

1. Two dimensions: (items processed, resource remaining/used)
2. Resource constraint: weight, capacity, sum, count, budget
3. Binary/Multiple choice: take/skip, or how many times to take
4. Recurrence: dp[i][resource] = best(skip, take(s))
5. Goal: Optimize (max/min) or count ways under constraint

Key Insight: You're allocating a limited resource across items. The constraint is what makes it DP—without it, greedy might work!

---

Classic Loop Structure

// Bounded (0/1) Knapsack
for (int i = 1; i <= n; i++) {           // items
    for (int w = 1; w <= capacity; w++) { // resource
        dp[i][w] = Math.max(
            dp[i-1][w],                    // skip item i
            dp[i-1][w-cost] + value       // take item i (previous row!)
        );
    }
}

// Unbounded Knapsack
for (int i = 1; i <= n; i++) {           // items
    for (int w = 1; w <= capacity; w++) { // resource
        dp[i][w] = Math.max(
            dp[i-1][w],                    // skip item i
            dp[i][w-cost] + value         // take item i (same row!)
        );
    }
}

---

Bounded vs Unbounded

CRITICAL DIFFERENCE

Bounded (0/1): Each item used at most once

for (int i = 1; i <= n; i++) {
    for (int w = capacity; w >= cost[i]; w--) {  // reverse order!
        dp[w] = Math.max(dp[w], dp[w - cost[i]] + value[i]);
    }
}

Unbounded: Each item used unlimited times

for (int i = 1; i <= n; i++) {
    for (int w = cost[i]; w <= capacity; w++) {  // forward order!
        dp[w] = Math.max(dp[w], dp[w - cost[i]] + value[i]);
    }
}

Key Difference:

• Bounded: dp[i-1][...] (previous row)
• Unbounded: dp[i][...] (same row—can reuse!)

---

Pattern Recognition Checklist

USE THIS CHECKLIST

When you see a new problem, ask:

• Do I have a collection of items to choose from?
• Is there a limited resource (capacity, budget, sum, count)?
• Does each item have a cost (weight, size, value)?
• Do I need to optimize (max/min) or count ways?
• Can I define dp[i][resource] as "best answer using first i items with resource constraint"?
• Does each item have a choice: take or skip?

If all YES → Pattern 3: Bounded Knapsack

---

Common Mistakes

COMMON PITFALLS

Mistake 1: Bounded vs Unbounded confusion

// WRONG - using unbounded logic for bounded problem
dp[i][w] = Math.max(dp[i][w], dp[i][w-cost] + value);

// RIGHT - bounded uses previous row
dp[i][w] = Math.max(dp[i][w], dp[i-1][w-cost] + value);

Mistake 2: Not checking if item fits

// WRONG - may access negative index
dp[i][w] = dp[i-1][w-cost] + value;

// RIGHT - check constraint first
if (w >= cost) {
    dp[i][w] = Math.max(dp[i][w], dp[i-1][w-cost] + value);
}

Mistake 3: Base case initialization

// For "minimum" problems
Arrays.fill(dp[0], Integer.MAX_VALUE);
dp[0][0] = 0;

// For "count ways" problems
dp[0][0] = 1;  // one way to make sum 0

// For "can we make" problems
dp[0][0] = true;

---

Space Optimization

FROM O(n×W) TO O(W)

Observation: Each row only depends on the previous row.

2D → 1D (Bounded):

// Before: O(n × W)
int[][] dp = new int[n + 1][W + 1];

for (int i = 1; i <= n; i++) {
    for (int w = W; w >= weight[i]; w--) {  // REVERSE!
        dp[i][w] = Math.max(
            dp[i-1][w],
            dp[i-1][w - weight[i]] + value[i]
        );
    }
}

// After: O(W)
int[] dp = new int[W + 1];

for (int i = 1; i <= n; i++) {
    for (int w = W; w >= weight[i]; w--) {  // REVERSE!
        dp[w] = Math.max(
            dp[w],                          // old dp[w] = dp[i-1][w]
            dp[w - weight[i]] + value[i]    // old value = dp[i-1][w-weight]
        );
    }
}

Why reverse? To avoid overwriting values we still need!

---

Learning Path

RECOMMENDED ORDER

Week 1: Core Knapsack (Problems 1-5)

• Master classic 0/1 Knapsack
• Learn Partition/Subset Sum pattern
• Understand bounded vs unbounded

Week 2: Coin Change (Problems 6-10)

• Practice unbounded knapsack
• Learn counting vs optimization
• Master order-dependent variations

Week 3: Subset Selection (Problems 11-15)

• Advanced state tracking (bitmask)
• Multiple knapsacks
• Complex constraints

Week 4: String/Sequence (Problems 16-20)

• Apply knapsack to strings
• Multiple choices per item
• Job scheduling patterns

Total: 20 problems × 4 weeks = Pattern 3 mastery

---

Quick Reference Table

Problem	State	Resource	Operation	Pattern Type
0/1 Knapsack	max value with i items, w capacity	weight	max(skip, take)	Classic
Partition Sum	can make sum with i items	sum	OR(skip, take)	Boolean
Target Sum	ways to reach sum with i items	sum	+(skip +, skip -)	Counting
Coin Change	min coins for amount with i coins	amount	min(skip, take)	Unbounded Min
Coin Change II	ways for amount with i coins	amount	+(skip, take)	Unbounded Count
Ones/Zeroes	max subset with i items, m 0s, n 1s	zeros, ones	max(skip, take)	2D Resource
Dice Rolls	ways to get sum with i dice	sum, dice	sum(all faces)	Bounded Count
Max Coins	max value from i piles, k coins	piles, coins	max(take 0..n)	Multi-choice

---

Detection Pattern Summary

QUICK IDENTIFICATION

See these keywords → Think Knapsack:

1. "Subset" + "sum" → Partition/Target Sum variant
2. "Coins" + "amount" → Coin Change variant
3. "Capacity" + "weight" + "value" → Classic Knapsack
4. "At most" + "budget/limit" → Resource constraint
5. "Ways to" + "target/sum" → Counting variant
6. "Minimum/Maximum" + "select items" → Optimization variant

All lead to: dp[items][resource] = best(skip, take(s))

---

Next Steps

AFTER MASTERING PATTERN 3

You're ready for:

• Pattern 4: Interval DP (range-based problems)
• Pattern 5: State Machine DP (mode transitions)
• Advanced Knapsack (multi-dimensional constraints)

Connection to Previous Patterns:

• Pattern 1: 1D state (position only)
• Pattern 2: 2D state (two positions)
• Pattern 3: 2D state (items + resource) ← New dimension type!

---

Final Thoughts

KNAPSACK IS EVERYWHERE

Bounded Knapsack is the most powerful optimization pattern in DP.

Master these 20 problems, and you'll:

• Recognize "this is a knapsack problem" instantly
• Know when to use bounded vs unbounded
• Transform problems into knapsack formulation
• Handle multiple resource constraints
• See connections to subset, partition, coin problems

This is your resource allocation foundation. Build it strong.

---

Summary: The Knapsack Template

// Classic 0/1 Knapsack Template
public int knapsack(int[] items, int[] costs, int capacity) {
    int n = items.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            // Always have option to skip
            dp[i][w] = dp[i-1][w];

            // Take if it fits
            if (costs[i-1] <= w) {
                dp[i][w] = Math.max(
                    dp[i][w],
                    dp[i-1][w - costs[i-1]] + items[i-1]
                );
            }
        }
    }

    return dp[n][capacity];
}

REMEMBER THE MANTRA

"For each item, try skipping it or taking it (if resource allows). Build the answer from smaller subproblems."

This is the essence of knapsack DP.