Knapsack Problems

The Treasure Hunter’s Guide to Knapsack Problems 🎒

Imagine you’re a treasure hunter with a magical backpack. The backpack can only hold a certain weight, but every treasure has a different weight and value. How do you pick the BEST treasures to carry home?

What Are Knapsack Problems?

Think of your school bag. It can only hold so much stuff before it gets too heavy. Now imagine you have:

• A heavy math book (worth a lot for your grades)
• A light notebook (worth less but easy to carry)
• A medium lunchbox (super important!)

The Question: Which items do you pick to get the MOST value without breaking your bag?

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

graph TD
    A["🎒 Your Bag<br>Limited Space"] --> B{What to pick?}
    B --> C["💎 Heavy Gold<br>High Value"]
    B --> D["💍 Light Ring<br>Medium Value"]
    B --> E["📿 Medium Gem<br>Good Value"]

The Three Types of Knapsack Problems

1. The 0-1 Knapsack Problem

The Story

You’re at a treasure cave. Each treasure can ONLY be picked ONCE — you either take it (1) or leave it (0). That’s why it’s called “0-1”!

Simple Example

Your bag capacity: 7 kg

Question: What’s the maximum value you can carry?

Answer: Take Crown (3kg, $4) + Necklace (4kg, $5) = 7kg total, $9 value!

Or: Crown (3kg, $4) + Ring (2kg, $3) = 5kg, $7 value… Not as good!

How Does It Work? (The DP Table Magic)

We build a table that answers: “If I had X kg capacity and could choose from first Y items, what’s the best value?”

The Magic Formula

For each item, we ask two questions:

1. Skip it: Keep the best value we had before
2. Take it: Add this item’s value to what we could fit before

Pick whichever is bigger!

// For each item and capacity
if (item weight <= current capacity) {
  best = max(
    skip it,
    take it + remaining space value
  )
}

Building the Table

Capacity →    0   1   2   3   4   5   6   7
──────────────────────────────────────────
No items      0   0   0   0   0   0   0   0
+Crown(3,$4)  0   0   0   4   4   4   4   4
+Necklace     0   0   0   4   5   5   5   9
+Ring         0   0   3   4   5   7   8   9
                                        ↑
                              Answer: $9!

The Code (Simple Version)

function knapsack01(W, weights, values) {
  const n = weights.length;
  const dp = Array(n + 1).fill(null)
    .map(() => Array(W + 1).fill(0));

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

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

2. The Unbounded Knapsack Problem

The Story

Now imagine a candy store where you can buy AS MANY of each candy as you want! The shelf never runs out. How do you fill your bag with maximum yumminess?

Key Difference from 0-1

Simple Example

Your bag capacity: 8 kg

Question: What’s the maximum value?

Think: We can take multiple apples! 4 Apples = 8kg, $12

Or: 1 Watermelon + 1 Orange = 8kg, $11

Best Answer: 4 Apples = $12!

The Magic Formula

Instead of looking at the “previous row” (without this item), we look at the “current row” (where we might have already taken this item):

graph TD
    A["Can I fit this item?"] -->|Yes| B["Two choices"]
    B --> C["Skip: keep dp of w"]
    B --> D["Take: value + dp of w-weight"]
    C --> E["Pick the MAX"]
    D --> E
    A -->|No| F["Keep previous best"]

The Code

function unboundedKnapsack(W, weights, values) {
  const n = weights.length;
  const dp = Array(W + 1).fill(0);

  for (let w = 1; w <= W; w++) {
    for (let i = 0; i < n; i++) {
      if (weights[i] <= w) {
        // Can keep adding same item!
        dp[w] = Math.max(
          dp[w],
          values[i] + dp[w - weights[i]]
        );
      }
    }
  }
  return dp[W];
}

Notice: We use dp[w - weights[i]] from the SAME array (not previous row), allowing infinite copies!

3. The Coin Change Problem

The Story

You’re at a vending machine. A snack costs exactly $11. You have unlimited coins of $1, $3, and $5. What’s the FEWEST coins needed?

Two Versions

Version 1: Minimum Coins

Target: $11 Coins: $1, $3, $5

Building the Solution

For each amount (0 to 11), find minimum coins needed:

Amount:  0  1  2  3  4  5  6  7  8  9  10  11
Coins:   0  1  2  1  2  1  2  3  2  3   2   3

How?

• Amount 3: Use one $3 coin → 1 coin
• Amount 5: Use one $5 coin → 1 coin
• Amount 11: Use $5+$5+$1 → 3 coins ✓

graph TD
    A["$11 target"] --> B["Try $1"]
    A --> C["Try $3"]
    A --> D["Try $5"]
    B --> E["$10 + 1 coin"]
    C --> F["$8 + 1 coin"]
    D --> G["$6 + 1 coin"]
    G --> H["Best: 3 coins total"]

The Code (Minimum Coins)

function minCoins(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0 coins for $0

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] !== Infinity) {
        dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

// Example: minCoins([1,3,5], 11) → 3

Version 2: Count Ways

Question: How many different ways to make $5 using $1 and $2 coins?

All the Ways

1. $1 + $1 + $1 + $1 + $1 (five $1s)
2. $1 + $1 + $1 + $2 (three $1s + one $2)
3. $1 + $2 + $2 (one $1 + two $2s)

Answer: 3 ways!

The Code (Count Ways)

function countWays(coins, amount) {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1; // One way to make $0

  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {
      dp[a] += dp[a - coin];
    }
  }

  return dp[amount];
}

// Example: countWays([1,2], 5) → 3

The Big Picture

graph LR
    A["🎒 Knapsack Family"] --> B["0-1 Knapsack"]
    A --> C["Unbounded Knapsack"]
    A --> D["Coin Change"]

    B --> B1["Each item once"]
    B --> B2["Maximize value"]

    C --> C1["Unlimited copies"]
    C --> C2["Maximize value"]

    D --> D1["Unlimited coins"]
    D --> D2["Min coins OR count ways"]

Quick Comparison

Why This Matters

These problems appear EVERYWHERE:

• Video Games: Best items for inventory slots
• Shopping: Best items within budget
• Investing: Best stocks within money limit
• Packing: Best items for luggage weight

Remember This!

Dynamic Programming = Breaking big problems into smaller ones, saving answers so we don’t repeat work!

Every knapsack problem asks: “For each capacity, what’s the best I can do?”

We build up from small capacities to big ones, using our previous answers.

That’s the magic! ✨

You’re now a Knapsack Problem treasure hunter! Go optimize those bags! 🎒💎