Knapsack Problems

🎒 The Knapsack Adventure: Packing for Treasure!

Imagine you’re going on a treasure hunt! You have a magical backpack (knapsack) that can only hold a certain weight. There are amazing treasures everywhere, but you can’t take them all. How do you pick the BEST treasures to make your adventure the most rewarding?

This is exactly what Knapsack Problems teach us!

🌟 The Big Picture

Think of it like this:

You’re packing a school bag. It can only hold 5 kg. You have books, toys, snacks, and a water bottle. Each item has a weight and a “happiness value” (how much you want it). You want to pack items that give you the MOST happiness without breaking your bag!

Dynamic Programming (DP) helps us solve this by remembering what we’ve already figured out, so we don’t do the same work twice.

🎯 What You’ll Learn

1. 0/1 Knapsack - Each treasure: take it OR leave it (no cutting allowed!)
2. Unbounded Knapsack - Take as many copies as you want
3. Coin Change Problem - Making exact change with fewest coins

📦 Knapsack 0/1: Take It or Leave It

The Story

You’re at a yard sale with exactly $10 in your pocket. There are 4 toys:

Goal: Get the MOST fun points with your $10!

The Magic Trick

We build a table. Each cell asks: “What’s the best I can do with THIS much money and THESE items?”

graph TD
    A["Start: $0, 0 fun"] --> B{Consider Car $4}
    B -->|Skip it| C["Keep current best"]
    B -->|Take it| D["Add 5 fun, use $4"]
    C --> E{Consider Guitar $5}
    D --> E
    E --> F["...continue for all items"]
    F --> G["Final Answer!"]

The Code Pattern

// capacity = your budget
// weights = price of each item
// values = fun points of each item

int[][] dp = new int[n+1][capacity+1];

for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= capacity; w++) {
        // Skip this item
        dp[i][w] = dp[i-1][w];

        // Take this item (if it fits)
        if (weights[i-1] <= w) {
            int take = values[i-1]
                     + dp[i-1][w - weights[i-1]];
            dp[i][w] = Math.max(dp[i][w], take);
        }
    }
}
// Answer: dp[n][capacity]

Why “0/1”?

Because each item is either:

• 0 = You DON’T take it
• 1 = You DO take it

No half-toys allowed! 🎮

🔑 Key Insight

Each item is considered ONCE. When you take an item, you look at dp[i-1] (the row ABOVE), meaning you can’t use that item again.

🔄 Unbounded Knapsack: Infinite Supply!

The Story

Now imagine a candy store! Each type of candy has unlimited pieces. Your bag can hold 10 kg. Each candy type has a weight and yumminess score.

You can take 5 lollipops, or 3 chocolates, or mix them!

What’s Different?

In 0/1 Knapsack: “Once I take the car, it’s gone.”

In Unbounded: “I can take another chocolate… and another… and another!”

graph TD
    A["Bag: 10 kg space"] --> B{Add Chocolate 3kg?}
    B -->|Yes!| C["7 kg left, +5 yummy"]
    C --> D{Add another Chocolate?}
    D -->|Yes!| E["4 kg left, +5 yummy"]
    E --> F{Add another?}
    F -->|Yes!| G["1 kg left, +5 yummy"]
    G --> H[Can't fit more. Done!]

The Code Pattern

// Notice: just 1D array!
int[] dp = new int[capacity + 1];

for (int i = 0; i < n; i++) {
    for (int w = weights[i]; w <= capacity; w++) {
        // Can take same item again!
        dp[w] = Math.max(dp[w],
                dp[w - weights[i]] + values[i]);
    }
}
// Answer: dp[capacity]

🔑 Key Difference

The Secret

When we use dp[w - weights[i]] from the same loop iteration, we might have already added this item. That means we can add it again!

💰 Coin Change Problem: Making Exact Change

The Story

You’re at an arcade! Games cost different amounts. You have coins: 1, 5, and 7 tokens.

Question 1: What’s the FEWEST coins to make exactly 11 tokens?

Question 2: How MANY different ways can you make 11 tokens?

Minimum Coins (Type 1)

Think of it as: “What’s the laziest way to pay?”

Making 11:
- 11 × (1 coin) = 11 coins 😫
- 1×7 + 4×1 = 5 coins 😕
- 1×7 + 1×(4)... wait, no 4 coin!
- 1×5 + 1×5 + 1×1 = 3 coins 😊
- 1×7 + 2×(2)... no 2 coin either
- Actually: 1×7 + 1×1 + 1×1 + 1×1 + 1×1 = 5
- Best: 7 + 1 + 1 + 1 + 1 = 5 coins?
- Wait! 5 + 5 + 1 = 3 coins! ✅

The Code Pattern

int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // Impossible
dp[0] = 0; // 0 coins for $0

for (int coin : coins) {
    for (int a = coin; a <= amount; a++) {
        // Use this coin + best way
        // to make the rest
        dp[a] = Math.min(dp[a],
                        1 + dp[a - coin]);
    }
}
// dp[amount] = fewest coins
// If dp[amount] > amount, impossible!

Counting Ways (Type 2)

Different question: “How many WAYS to make exact change?”

int[] dp = new int[amount + 1];
dp[0] = 1; // 1 way to make $0: use nothing

for (int coin : coins) {
    for (int a = coin; a <= amount; a++) {
        // Add ways using this coin
        dp[a] += dp[a - coin];
    }
}
// dp[amount] = total number of ways

graph TD
    A["Target: 11 tokens"] --> B["Use coin 1?"]
    A --> C["Use coin 5?"]
    A --> D["Use coin 7?"]
    B --> E["Now make: 10"]
    C --> F["Now make: 6"]
    D --> G["Now make: 4"]
    E --> H["Keep breaking down..."]
    F --> H
    G --> H
    H --> I["Reach 0 = Found a way!"]

🔑 Key Insight

• Minimum coins: Use Math.min() - we want the smallest number
• Count ways: Use += - we’re adding up all possibilities
• Both are Unbounded - same coin can be used many times!

🧠 The DP Thinking Framework

For ANY Knapsack Problem, Ask:

1. What am I optimizing? (Max value? Min coins? Count ways?)
2. Can I reuse items? (0/1 vs Unbounded)
3. What’s my constraint? (Weight? Amount? Count?)

The Pattern

// Initialize dp array
// dp[0] = base case (usually 0 or 1)

for (each item/coin) {
    for (each capacity from item_weight to max) {
        // Decision: skip or use this item
        dp[capacity] = best of (skip, use);
    }
}

return dp[max_capacity];

🎮 Quick Examples

Example 1: 0/1 Knapsack

Capacity: 7 kg
Items: [(3kg, $4), (4kg, $5), (2kg, $3)]

Best: Take items 1 and 3
      3+2 = 5 kg, 4+3 = $7 value

Example 2: Unbounded Knapsack

Capacity: 8 kg
Items: [(2kg, $3), (3kg, $4)]

Best: Take 4 of the 2kg item
      4×2 = 8 kg, 4×3 = $12 value

Example 3: Coin Change

Coins: [1, 3, 4]
Target: 6

Minimum: 2 coins (3+3)
Ways: 4 ways
  → 1+1+1+1+1+1
  → 1+1+1+3
  → 3+3
  → 1+1+4

🌈 Remember This!

💪 You’ve Got This!

Think of DP like building with LEGO:

• Each small piece (subproblem) connects to others
• You build from the bottom up
• The final structure (answer) emerges naturally!

The magic: Once you solve a small piece, you NEVER solve it again. You just look it up!

🎒 Next time you pack a bag, remember: you just solved a famous computer science problem!