My Greedy Algorithm Said No. It Was Wrong.

Two days ago I wrote a function called packMaxExact for a cleanup job. It works, it's safe, and it's quietly wrong more often than I'd like. This post is me figuring out how wrong, and what the proper version costs.

The problem

Picture a points ledger. Users get credited points, which are positive rows, and spend them, which are negative rows. Over time a user collects a lot of small rows, and every balance query has to walk all of them.

The cleanup job looks at one credit, say +1000, and tries to find spends that add up to exactly 1000. If it finds them, it marks the credit and those spends as settled, together, in one transaction. The balance doesn't change, because the settled rows sum to zero, but there are fewer live rows to deal with.

To make the search easier, the spends are grouped by amount first. So the input looks like this:

// "I have two spends of 750, three of 300, forty of 30 and twenty of 10"
const occurrences = [
  { value: 750, count: 2 },
  { value: 300, count: 3 },
  { value: 30, count: 40 },
  { value: 10, count: 20 },
]

And the question is: can I pick some of these, never more than count of each value, so they add up exactly to 1000? If yes, which ones?

If this sounds like making change with a limited supply of each coin, that's exactly what it is.

What I wrote

I did the obvious thing: take the biggest values first, as many as fit, then move on to smaller ones.

type Occurrence = { value: number; count: number }

function packGreedy(
  capacity: number,
  occurrences: Occurrence[], // sorted by value, largest first
): Map<number, number> | null {
  let remaining = capacity
  const result = new Map<number, number>()

  for (const { value, count } of occurrences) {
    if (remaining <= 0) break
    if (value > remaining) continue

    const take = Math.min(count, Math.floor(remaining / value))
    if (take > 0) {
      result.set(value, take)
      remaining -= take * value
    }
  }

  return remaining === 0 ? result : null
}

For 1000 with the list above, it takes one 750, eight 30s and one 10. That's 750 + 240 + 10, exactly 1000.

And I knew it was a shortcut. The comment I left in the real code says:

// If greedy left a remainder, we treat it as "no exact fit possible"

"Treat it as" is doing a lot of work in that sentence.

Where it breaks

Here's a case with nothing unusual about it:

capacity: 30
available: 25 x 1, 10 x 3

Greedy grabs the 25, because it's the biggest thing that fits. Now it needs 5, nothing is that small, so it returns null. Meanwhile 10 + 10 + 10 was sitting right there.

A couple more:

600 from 400 x 1, 300 x 2   -> greedy: null, actual answer: 300 + 300
 60 from  25 x 2,  20 x 3   -> greedy: null, actual answer: 20 + 20 + 20

The pattern is always the same. Taking the big value first feels like progress, but it can leave a remainder that the smaller values can't cover, even though a different mix would have worked perfectly.

You might remember that greedy change-making works fine for normal coins. That's true for the classic version, where you have unlimited coins of each type and denominations designed to cooperate. The moment each value has a limited count, or the values are whatever amounts happened to show up in a database, that guarantee is gone.

So how often is it wrong?

The failure is easy to see in an example. What I actually wanted to know was whether it's an occasional edge case or a regular thing.

So I ran an experiment. I generated random inventories, and for each one I built the target amount from a random subset of it. That way an exact answer is guaranteed to exist, and any null from greedy is a miss. I ran 20,000 trials for each of three kinds of inventory:

These distributions are made up, and real ledger data won't match any of them exactly. But even the friendliest case, round amounts with a 10 always available to fill gaps, misses roughly one solvable case in nine. With messy values, greedy is wrong more often than it's right.

That's not an edge case. That's a coin flip that usually lands the wrong way.

Why it didn't cause a real bug

One thing greedy does get right: when it does return an answer, the answer is valid. I checked that in every trial. The chosen values always add up exactly and never use more than the available count.

So its failure mode is safe. It never settles the wrong rows. It just says "no" and the job skips that credit.

But "safe" still has a cost. Every wrong "no" is a set of rows that never gets cleaned up, and the job will say "no" again on the next run, and the one after that. The whole point of the job was fewer live rows, and the shortcut was leaving a lot of them behind.

The exact version

The fix is a classic bit of dynamic programming: bounded subset sum. The idea is to build up a table of every total you can reach, one value at a time.

Start with just 0 reachable, using nothing. Then, for each value, sweep through the totals from small to large. A total sum becomes reachable if sum - value was reachable and we haven't used up this value's count getting there.

The one clever part is counting copies without a nested loop. While sweeping a value, used[sum] records how many copies of this value it took to reach sum in this pass. Reaching sum from sum - value costs one more copy than sum - value did. If that would go over count, you can't extend that path.

function packExact(
  capacity: number,
  occurrences: Occurrence[],
): Map<number, number> | null {
  // item[s] is the index of the occurrence that first reached sum s, or -1
  const item = new Int32Array(capacity + 1).fill(-1)
  const reached = new Uint8Array(capacity + 1)
  reached[0] = 1

  // used[s] is how many copies of the current value it took to reach s
  const used = new Int32Array(capacity + 1)

  occurrences.forEach(({ value, count }, index) => {
    used.fill(0)
    for (let sum = value; sum <= capacity; sum++) {
      const from = sum - value
      if (!reached[sum] && reached[from] && (used[from] ?? 0) < count) {
        reached[sum] = 1
        used[sum] = (used[from] ?? 0) + 1
        item[sum] = index
      }
    }
  })

  if (!reached[capacity]) return null

  const result = new Map<number, number>()
  for (let sum = capacity; sum > 0; ) {
    const occurrence = occurrences[item[sum] ?? -1]
    if (!occurrence) throw new Error(`Broken path at ${sum}`)
    result.set(occurrence.value, (result.get(occurrence.value) ?? 0) + 1)
    sum -= occurrence.value
  }
  return result
}

item works like a trail of breadcrumbs. For every total, it remembers which value got there first. Once the target is reachable, you walk backwards from it: look up which value reached this total, subtract it, and repeat until you hit zero. The values you stepped through are the answer.

A total is only ever set once, the first time it becomes reachable, so the trail can never loop or contradict itself. Walking back through one value's pass never takes more than count steps, because that's exactly what used prevented.

On the earlier examples, it finds 300 + 300 for 600, 20 + 20 + 20 for 60, and 10 + 10 + 10 for 30.

The ?? 0 and ?? -1 are there because I wrote the code in this post with noUncheckedIndexedAccess turned on, which treats every array read as possibly undefined. It's a little noisy here, but I like what that setting catches everywhere else.

How I know it's right

I don't trust a dynamic programming function because it looks correct. I trust it after it agrees with a brute-force version that's too slow to use but too simple to get wrong:

function canPackBrute(capacity: number, occurrences: Occurrence[], i = 0): boolean {
  if (capacity === 0) return true
  const occurrence = occurrences[i]
  if (!occurrence) return false

  const most = Math.min(occurrence.count, Math.floor(capacity / occurrence.value))
  for (let take = most; take >= 0; take--) {
    if (canPackBrute(capacity - take * occurrence.value, occurrences, i + 1)) return true
  }
  return false
}

Across all three distributions, I compared the two on thousands of random inputs, including targets that can't be packed. packExact found an answer every time brute force said one existed, returned null every time brute force said none did, and every answer it returned was valid.

What it costs

The exact version does one pass over every total from 0 to the target, once per distinct value. So the time is roughly distinct values x target amount, and memory is about 9 bytes per unit of the target, across the three arrays.

Rough numbers from single runs on my laptop:

For point amounts in the thousands, that's nothing. It does depend on the amounts being integers and not astronomically large. For money, you'd work in cents. If a single target could be in the hundreds of millions, I'd want a different approach, or at least a cap on it.

What I'd do instead

Since greedy is basically free and usually right on friendly data, I don't need to throw it away. I only need to stop trusting its "no":

function packHybrid(capacity: number, occurrences: Occurrence[]) {
  return packGreedy(capacity, occurrences) ?? packExact(capacity, occurrences)
}

Greedy answers the easy cases instantly. The exact version only runs when greedy gives up, which is exactly when greedy might be lying.

There's one subtle difference worth knowing. The two don't necessarily pick the same combination. Greedy tends to use big values, which means fewer rows. The exact version returns a valid combination, not necessarily the one with the fewest rows. For settling ledger rows that doesn't matter to me. If it mattered to you, you'd track the minimum number of items for each total instead of just whether it's reachable, which is a slightly bigger table and the same basic idea.

What I took from this

The comment in my original code was honest. It said greedy "treats" a remainder as impossible. What it didn't say was how often that treatment is wrong, and I didn't know until I measured it.

A few things I want to remember:

• Greedy is only correct for problems that have been shown to work with greedy. "Take the biggest first" is a strategy, not a proof.
• A safe failure is still a failure. Nothing got corrupted, but the job was silently not doing the one thing it existed to do.
• Measure the shortcut before you trust it. Twenty lines of random testing turned "probably fine" into "wrong two times out of three on messy data".
• Keep a brute-force version around. It's the cheapest way to trust the clever one.

It's a small function, but I like that the fix didn't mean replacing the fast path. It meant not believing it when it says no.