Knapsack Problems

🎒 The Magical Backpack Adventure: Mastering Knapsack Problems

The Story Begins…

Imagine you’re going on the greatest treasure hunt ever! 🏴‍☠️

You find a magical cave filled with treasures—gold coins, sparkling gems, ancient scrolls. But here’s the twist: your backpack can only carry a certain weight.

You can’t take everything. So what do you grab to get the most valuable loot?

This, dear adventurer, is the Knapsack Problem—one of the most famous puzzles in computer science!

🧠 What is Dynamic Programming?

Before we dive into our treasure hunt, let’s understand our secret weapon: Dynamic Programming (DP).

Think of DP like this:

🧒 “Instead of solving a big puzzle all at once, I break it into tiny puzzles. I remember the answers to tiny puzzles so I don’t solve them again!”

Real-life Example:

• Your mom asks: “What’s 2+2?” You say “4!”
• She asks: “What’s 2+2+3?”
• Instead of starting from scratch, you think: “I already know 2+2=4. So it’s 4+3=7!”

That’s DP! Remember small answers. Use them for bigger answers.

🎒 The 0-1 Knapsack Problem

The Rules of This Game

You find 3 treasures in the cave:

Your backpack holds 5 kg max.

The 0-1 Rule: For each item, you can either:

• Take it (1)
• Leave it (0)

No cutting diamonds in half! No taking half a crown!

How Do We Solve This?

Let’s build a magic table that remembers answers!

Step 1: Create a grid

• Rows = items (Crown, Diamond, Scroll)
• Columns = weights (0, 1, 2, 3, 4, 5 kg)

Step 2: Fill it cell by cell

For each cell, ask: “What’s the max value I can get with this weight limit, using items so far?”

        0kg  1kg  2kg  3kg  4kg  5kg
None:   $0   $0   $0   $0   $0   $0
Crown:  $0   $0   $3   $3   $3   $3
+Dia:   $0   $0   $3   $4   $4   $7
+Scrl:  $0   $0   $3   $4   $5   $7

The Magic Formula:

For each item, we ask:

“Should I take this item or leave it?”

If item weight > bag capacity:
    Can't take it! Keep previous best.

Otherwise:
    Option A: Don't take it (keep prev best)
    Option B: Take it (item value + best
              value with remaining space)

    Pick the BIGGER option!

The Answer!

With 5kg capacity: $7 (Crown + Diamond) 🎉

Python Code: 0-1 Knapsack

def knapsack_01(weights, values, capacity):
    n = len(weights)
    # Create table: (n+1) rows, (capacity+1) cols
    dp = [[0] * (capacity + 1)
          for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Item index is i-1 (0-indexed)
            if weights[i-1] <= w:
                # Take it OR leave it?
                take = values[i-1] + dp[i-1][w - weights[i-1]]
                leave = dp[i-1][w]
                dp[i][w] = max(take, leave)
            else:
                # Too heavy! Leave it.
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

# Example
weights = [2, 3, 4]
values = [3, 4, 5]
capacity = 5
print(knapsack_01(weights, values, capacity))
# Output: 7

🔄 The Unbounded Knapsack Problem

A New Twist in Our Story!

Now imagine the cave has infinite copies of each treasure!

Backpack: 4 kg

New Rule: You can take as many of each item as you want!

The Difference

How to Solve It?

The magic formula changes slightly:

For each weight w from 0 to capacity:
    For each item:
        If item fits (weight <= w):
            dp[w] = max(dp[w],
                        value + dp[w - weight])

Key insight: We can keep adding the same item!

Let’s Fill the Table

Capacity:  0    1    2    3    4
Value:     $0   $1   $3   $4   $6
           ↑    ↑    ↑    ↑    ↑
         empty coin ring+ gem  2 rings!
                     coin

Answer: $6 (2 Rings!) 💍💍

Python Code: Unbounded Knapsack

def unbounded_knapsack(weights, values, capacity):
    n = len(weights)
    # Only need 1D array!
    dp = [0] * (capacity + 1)

    for w in range(1, capacity + 1):
        for i in range(n):
            if weights[i] <= w:
                # Can we do better by adding this item?
                dp[w] = max(dp[w],
                           values[i] + dp[w - weights[i]])

    return dp[capacity]

# Example
weights = [1, 2, 3]
values = [1, 3, 4]
capacity = 4
print(unbounded_knapsack(weights, values, capacity))
# Output: 6

🪙 The Coin Change Problem

A New Adventure!

You’re at a magical vending machine. A toy costs $11.

You have coins: $1, $5, $6

Question: What’s the minimum number of coins to make exactly $11?

Think Like a 5-Year-Old

“If I want $11, I could use a $6 coin. Then I need $5 more.” “For $5, I can use one $5 coin!” “So: $6 + $5 = $11 with just 2 coins!” 🎉

But wait—could we do better with three $1 coins and… no, that’s more coins!

The DP Table

We build a table where each cell says:

“Minimum coins needed to make this amount”

Amount:    0   1   2   3   4   5   6   7   8   9  10  11
Min coins: 0   1   2   3   4   1   1   2   3   4   2   2
           ↑               ↑   ↑               ↑   ↑
         zero           $5  $6            $5+$5  $5+$6

The Magic Formula

For each amount from 1 to target:
    For each coin:
        If coin <= amount:
            dp[amount] = min(dp[amount],
                            1 + dp[amount - coin])

Answer: 2 coins ($5 + $6) 🪙🪙

Python Code: Coin Change

def coin_change(coins, amount):
    # Initialize with "impossible" (amount+1)
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # 0 coins for $0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], 1 + dp[a - coin])

    # If still "impossible", return -1
    return dp[amount] if dp[amount] <= amount else -1

# Example
coins = [1, 5, 6]
amount = 11
print(coin_change(coins, amount))
# Output: 2

🎯 How They’re All Connected

All three problems share the same DP pattern:

graph TD
    A["Start with a target"] --> B["Break into smaller targets"]
    B --> C["Solve smallest first"]
    C --> D["Build up to answer"]
    D --> E["Remember everything!"]

🌟 Key Takeaways

1. Dynamic Programming = Smart Remembering

   • Solve small problems first
   • Store answers in a table
   • Build up to the big answer

2. 0-1 Knapsack

   • Each item: take once or leave
   • Use 2D table
   • Ask: “Take it or leave it?”

3. Unbounded Knapsack

   • Each item: take unlimited times
   • Use 1D table (simpler!)
   • Ask: “How many times?”

4. Coin Change

   • Find minimum coins
   • Like unbounded, but minimize count
   • Ask: “What’s the fewest?”

🚀 You Did It!

You’ve just learned some of the most important algorithms in computer science!

These patterns appear everywhere:

• 📦 Packing trucks efficiently
• 💰 Making change at stores
• 🎮 Resource management in games
• 📊 Budget optimization

Remember: Start small, remember answers, build up!

Now go forth and pack those knapsacks! 🎒✨