Knapsack-style Problems

The art of strategy is knowing what to take and what to leave behind, especially when you can't carry everything.

Imagine you're a thief with a knapsack. You're in a room full of treasures, each with a specific weight and value. Your knapsack has a strict weight limit. How do you choose which items to steal to maximize your total profit? This is the classic 0/1 Knapsack Problem, a cornerstone of dynamic programming that teaches how to make optimal choices under constraints. "0/1" means that for each item, you have two choices: either take it (1) or leave it (0).

The Brute-Force Recursive Approach

The most intuitive way to think about this is to try every possibility. For each item, we can either include it in our knapsack or not. This leads to a recursive solution.

knapsack(items, capacity):

Base Case: If there are no items left or the capacity is 0, the value is 0.
Recursive Step: For the current item:
1. If it's too heavy: We can't include it. The answer is knapsack(remaining_items, capacity).
2. If it fits: We have two choices:
  - Don't take it: The value is knapsack(remaining_items, capacity).
  - Take it: The value is value_of_current_item + knapsack(remaining_items, capacity - weight_of_current_item). We return the max of these two choices.

This approach has a time complexity of $O(2^N)$ , as it explores two branches for each of the N items. This is far too slow for anything but a tiny number of items.

The Dynamic Programming Solution

The brute-force approach is slow because it repeatedly solves the same subproblems. The state of any subproblem is defined by two things:

Which items we are allowed to consider (e.g., the first i items).
The remaining capacity of the knapsack (w).

This structure is a perfect fit for a 2D DP table.

Walkthrough: Building the DP Table

Define DP State: We'll create a 2D array, dp, where dp[i][w] represents the maximum value we can achieve using items from the first i items, with a total weight capacity of w.
The Recurrence Relation: For each item i and each possible weight w from 0 to W:
- Choice 1: Don't include item i. If we don't take the i-th item, the maximum value is simply the best we could do with the previous i-1 items at the same capacity w. This value is dp[i-1][w].
- Choice 2: Include item i. We can only do this if w >= weight[i-1]. If we take it, the value is value[i-1] plus the best we could do with the previous i-1 items given the remaining capacity: values[i-1] + dp[i-1][w - weights[i-1]].
- dp[i][w] is the maximum of these two choices.
Iteration: We fill the table, and the final answer is the value in the bottom-right corner, dp[n][W].

def knapsack_01(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            # The current item's weight and value
            weight = weights[i-1]
            value = values[i-1]
            
            # If the item is too heavy, we can't include it.
            if weight > w:
                dp[i][w] = dp[i-1][w]
            else:
                # The max of either not including the item, or including it.
                dp[i][w] = max(dp[i-1][w], value + dp[i-1][w - weight])

    return dp[n][W]

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

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            int weight = weights[i-1];
            int value = values[i-1];
            
            if (weight > w) {
                dp[i][w] = dp[i-1][w];
            } else {
                dp[i][w] = Math.max(dp[i-1][w], value + dp[i-1][w - weight]);
            }
        }
    }
    return dp[n][W];
}

int knapsack01(const std::vector<int>& weights, const std::vector<int>& values, int W) {
    int n = weights.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            int weight = weights[i-1];
            int value = values[i-1];

            if (weight > w) {
                dp[i][w] = dp[i-1][w];
            } else {
                dp[i][w] = std::max(dp[i-1][w], value + dp[i-1][w - weight]);
            }
        }
    }
    return dp[n][W];
}

Fractional Knapsack

This is similar to the 0/1 Knapsack, but you can take fractions of items. The greedy approach works here:

Calculate the value-to-weight ratio for each item.
Sort items by this ratio in descending order.
Start adding items to the knapsack:
- If the item fits, take it all.
- If it doesn't fit, take the fraction that fits.

0/1 vs. Unbounded Knapsack

In the above variations, you can take each item at most once. A common variant is the Unbounded Knapsack problem, where you can use each item as many times as you like (like making change with an unlimited supply of each coin type).

The change to the DP recurrence is subtle but powerful. When you decide to take an item, you can still take that same item again.