Knapsack families · Capacity and loop direction¶

Knapsack is not one template. It is a family whose variants differ in item multiplicity, exactness, objective, and whether order matters.

Start with the contract¶

Choose one:

best[c] = maximum value with capacity at most c;
best[c] = maximum value with total weight exactly c;
possible[c] = whether exact weight c is reachable;
ways[c] = number of constructions for exact weight c;
fewest[c] = minimum number of items for exact weight c.

The initialization follows the words:

Contract	`state[0]`	Other states
max value, at most capacity	`0`	`0`
max value, exact capacity	`0`	negative infinity
feasibility, exact	`true`	`false`
count exact constructions	`1`	`0`
minimum items, exact	`0`	positive infinity

0/1 knapsack · Each item once¶

Natural 2D recurrence:

dp[i][c] = max(
    dp[i - 1][c],
    dp[i - 1][c - weight[i]] + value[i]
)

When compressed to one array, iterate capacity downward.

flowchart LR
  accTitle: Why zero-one knapsack capacity runs downward
  accDescr: While processing one item, a descending capacity loop reads lower capacities that have not yet been updated by this item, so the source belongs to the previous item layer. An ascending loop would read the current layer and reuse the item.
  A["process item (w, v)"] --> B["c = capacity down to w"]
  B --> C["read best[c - w]<br/>old item layer"]
  C --> D["best[c] = max(skip, take)"]
  D --> E["item used at most once"]

PythonC++17C++11

def knapsack_01(capacity: int, items: Iterable[tuple[int, int]]) -> int:
    """Return the maximum value when every item can be used at most once."""
    if capacity < 0:
        raise ValueError("capacity must be nonnegative")

    best = [0] * (capacity + 1)
    for weight, value in items:
        if weight <= 0:
            raise ValueError("item weights must be positive")
        # Descend so best[current - weight] still belongs to the prior item layer.
        for current in range(capacity, weight - 1, -1):
            best[current] = max(best[current], best[current - weight] + value)
    return best[capacity]

inline long long knapsack_01(
    int capacity, const std::vector<std::pair<int, int>>& items) {
  if (capacity < 0) {
    throw std::invalid_argument("capacity must be nonnegative");
  }
  std::vector<long long> best(capacity + 1, 0);
  for (const auto& item : items) {
    const int weight = item.first;
    const int value = item.second;
    if (weight <= 0) {
      throw std::invalid_argument("item weights must be positive");
    }
    // Descend so the source state still belongs to the prior item layer.
    for (int current = capacity; current >= weight; --current) {
      best[current] =
          std::max(best[current], best[current - weight] + value);
    }
  }
  return best[capacity];
}

inline long long knapsack_01(
    int capacity, const std::vector<std::pair<int, int>>& items) {
  if (capacity < 0) {
    throw std::invalid_argument("capacity must be nonnegative");
  }
  std::vector<long long> best(capacity + 1, 0);
  for (const auto& item : items) {
    const int weight = item.first;
    const int value = item.second;
    if (weight <= 0) {
      throw std::invalid_argument("item weights must be positive");
    }
    // Descend so the source state still belongs to the prior item layer.
    for (int current = capacity; current >= weight; --current) {
      best[current] =
          std::max(best[current], best[current - weight] + value);
    }
  }
  return best[capacity];
}

Complete or unbounded knapsack · Reuse allowed¶

Iterate capacity upward so best[c - weight] may already include the current item:

for each item:
    for c from weight to capacity:
        best[c] = improve(best[c], best[c - weight] + contribution)

LeetCode Coin Change asks for the minimum reusable coins, so the combine operation is MIN rather than MAX.

PythonC++17C++11

def minimum_coins(coins: Iterable[int], amount: int) -> int:
    """Return the fewest reusable coins totaling amount, or -1 if impossible."""
    if amount < 0:
        raise ValueError("amount must be nonnegative")
    denominations = list(coins)
    if any(coin <= 0 for coin in denominations):
        raise ValueError("coin values must be positive")

    impossible = amount + 1
    best = [impossible] * (amount + 1)
    best[0] = 0  # Zero coins make amount zero.
    for current in range(1, amount + 1):
        for coin in denominations:
            if coin <= current:
                # Append this reusable coin to a solved smaller amount.
                best[current] = min(best[current], best[current - coin] + 1)
    return -1 if best[amount] == impossible else best[amount]

inline int minimum_coins(const std::vector<int>& coins, int amount) {
  if (amount < 0) {
    throw std::invalid_argument("amount must be nonnegative");
  }
  for (const int coin : coins) {
    if (coin <= 0) {
      throw std::invalid_argument("coin values must be positive");
    }
  }

  const int impossible = amount + 1;
  std::vector<int> best(amount + 1, impossible);
  best[0] = 0;  // Zero coins make amount zero.
  for (int current = 1; current <= amount; ++current) {
    for (const int coin : coins) {
      if (coin <= current) {
        // Append this reusable coin to a solved smaller amount.
        best[current] = std::min(best[current], best[current - coin] + 1);
      }
    }
  }
  return best[amount] == impossible ? -1 : best[amount];
}

inline int minimum_coins(const std::vector<int>& coins, int amount) {
  if (amount < 0) {
    throw std::invalid_argument("amount must be nonnegative");
  }
  for (const int coin : coins) {
    if (coin <= 0) {
      throw std::invalid_argument("coin values must be positive");
    }
  }

  const int impossible = amount + 1;
  std::vector<int> best(amount + 1, impossible);
  best[0] = 0;  // Zero coins make amount zero.
  for (int current = 1; current <= amount; ++current) {
    for (const int coin : coins) {
      if (coin <= current) {
        // Append this reusable coin to a solved smaller amount.
        best[current] = std::min(best[current], best[current - coin] + 1);
      }
    }
  }
  return best[amount] == impossible ? -1 : best[amount];
}

Counting: combinations versus sequences¶

For reusable coins:

// Combinations: [1,2] and [2,1] are the same.
for coin in coins:
    for amount from coin upward:
        ways[amount] += ways[amount - coin]

// Ordered sequences: [1,2] and [2,1] are different.
for amount from 1 upward:
    for coin in coins:
        ways[amount] += ways[amount - coin]

The inner loop represents the final choice. Changing loop order changes which partial constructions are available, so it changes the problem solved.

Bounded knapsack · Each item has a count¶

If an item may be used at most count times:

Direct enumeration: try 0..count copies per state. Simple, potentially slow.
Binary splitting: replace count copies with 0/1 bundles of sizes 1, 2, 4, ..., plus a remainder.
Monotone-queue optimization: advanced option when capacity is large and transition structure supports it.

Binary splitting turns multiplicity 13 into bundles 1, 2, 4, 6; every use count from 0..13 can be represented by choosing bundles.

Subset sum and partition¶

Subset sum is 0/1 feasibility:

possible[0] = true
for value in values:
    for sum from target down to value:
        possible[sum] |= possible[sum - value]

Descending order is essential. For equal partition, the target is half the total sum; reject odd totals first.

If values can be negative, array indices no longer map directly to sums. Use an offset or a set/map of reachable sums, and include the enlarged range in the complexity.

Multiple-choice and grouped knapsack¶

When at most one option may be chosen from each group, every new group must read the table from before that group. Copy the old layer or use a fresh layer; an ordinary item loop can accidentally choose multiple options from one group.

Invariant: new[c] uses zero or one choice from the current group plus a solution from completed earlier groups.

Multiple resources¶

For weight and volume:

dp[weight][volume] = best value

For 0/1 items, descend both axes. Complexity is O(items × weight_limit × volume_limit), and memory is the product of the two limits.

Chooser¶

flowchart TD
  accTitle: Choosing a knapsack recurrence and loop order
  accDescr: First decide whether items are used once, without limit, or with a bounded count. Then decide whether the result is feasibility, count, minimum, or maximum and whether capacity must be exact. Use descending capacity for zero-one items, ascending capacity for reusable items, and a separate group layer for mutually exclusive options.
  A{"How often may each item be used?"}
  A -->|"once"| B["0/1: capacity descends"]
  A -->|"unlimited"| C["complete: capacity ascends"]
  A -->|"bounded count"| D["enumerate, binary split,<br/>or monotone queue"]
  A -->|"one per group"| E["fresh layer per group"]
  B --> F{"What is returned?"}
  C --> F
  D --> F
  E --> F
  F -->|"possible?"| G["boolean OR"]
  F -->|"how many?"| H["SUM; define order"]
  F -->|"fewest?"| I["MIN + infinity"]
  F -->|"best value?"| J["MAX; exact or at-most"]

Knapsack review checklist¶

Is capacity exact or merely an upper bound?
May the empty selection be the answer?
How many times may each item be used?
Does order distinguish solutions?
Which operation combines candidates: OR, SUM, MIN, or MAX?
What does the impossible sentinel mean?
Does every compressed loop read the intended item layer?