Counting with a knapsack

Lesson · 9 min read · Dynamic programming · Counting knapsack

Replace max with sum and the knapsack counts the ways instead of finding the best. The loop order decides whether you count combinations or sequences.

Max becomes sum

"In how many ways can amount a be paid with these coins?" is the unbounded knapsack with the operators swapped: instead of the best value over the choices, add up the number of ways over them. The base case is one way to pay 0: pay nothing.

Counting recurrence

ways(i, a)

ways(i − 1, a) (no more of coin i) + ways(i, a − coin[i]) (one more of coin i).

base cases

ways(·, 0) = 1; ways(0, a) = 0 for a > 0; negative amounts give 0.

Combinations, not sequences

As the recurrence lesson showed, looping over amounts on the outside and coins on the inside counts 1 + 2 and 2 + 1 separately: sequences. Putting coins on the outside processes each coin type once, in a fixed order, so each combination is built in exactly one way.

def count_ways(coins, amount):
    ways = [1] + [0] * amount
    for c in coins:                            # coins outside: combinations
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

long long count_ways(const std::vector<int>& coins, int amount) {
    std::vector<long long> ways(amount + 1, 0);
    ways[0] = 1;
    for (int c : coins)                            // coins outside: combinations
        for (int a = c; a <= amount; ++a)
            ways[a] += ways[a - c];
    return ways[amount];
}

static long countWays(int[] coins, int amount) {
    long[] ways = new long[amount + 1];
    ways[0] = 1;
    for (int c : coins)                            // coins outside: combinations
        for (int a = c; a <= amount; a++)
            ways[a] += ways[a - c];
    return ways[amount];
}

function countWays(coins, amount) {
    const ways = new Array(amount + 1).fill(0);
    ways[0] = 1;
    for (const c of coins)                         // coins outside: combinations
        for (let a = c; a <= amount; a++)
            ways[a] += ways[a - c];
    return ways[amount];
}

fn count_ways(coins: &[usize], amount: usize) -> u64 {
    let mut ways = vec![0u64; amount + 1];
    ways[0] = 1;
    for &c in coins {                              // coins outside: combinations
        for a in c..=amount {
            ways[a] += ways[a - c];
        }
    }
    ways[amount]
}

countWays :: [Int] -> Int -> Integer
countWays coins amount = last (foldl add (1 : replicate amount 0) coins)
  where
    -- coins outside: each coin joins every amount once, so orderings are not counted twice
    add ways c = elems row
      where
        old = listArray (0, amount) ways :: Array Int Integer
        row = listArray (0, amount)
          [ old ! a + (if a >= c then row ! (a - c) else 0) | a <- [0 .. amount] ] :: Array Int Integer

Coins 1, 2, 5; amount 5. One pass per coin type.

Step 1 / 4

ways
100102030405
One way to pay 0; no way yet to pay anything else.
Step 2 / 4

ways
101112131415
After allowing coin 1: ways[a] += ways[a − 1] for a from 1 up to 5.
Step 3 / 4

ways
101122233435
After allowing coin 2: ways[a] += ways[a − 2] for a from 2 up to 5.
Step 4 / 4

ways
101122233445
After allowing coin 5: ways[a] += ways[a − 5] for a from 5 up to 5. ways[5] = 4.

Implementation

In six languages:

def count_ways(amount, coins):
    ways = [1] + [0] * amount                # one way to make 0
    for c in coins:                          # coins outside: combinations, not sequences
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

#include <vector>

long long solve(int amount, const std::vector<int>& coins) {
    std::vector<long long> ways(amount + 1, 0);
    ways[0] = 1;
    for (int c : coins)                          // coins outside: combinations
        for (int a = c; a <= amount; ++a) ways[a] += ways[a - c];
    return ways[amount];
}

class Solution {
    public long countWays(int amount, int[] coins) {
        long[] ways = new long[amount + 1];
        ways[0] = 1;
        for (int c : coins)                        // coins outside: combinations
            for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
        return ways[amount];
    }
}

function countWays(amount, coins) {
  const ways = [1, ...new Array(amount).fill(0)];
  for (const c of coins)                       // coins outside: combinations
    for (let a = c; a <= amount; a++) ways[a] += ways[a - c];
  return ways[amount];
}

fn solve(amount: i64, coins: &[i64]) -> i64 {
    let n = amount as usize;
    let mut ways = vec![0i64; n + 1];
    ways[0] = 1;
    for &c in coins {                            // coins outside: combinations
        for a in (c as usize)..=n {
            ways[a] += ways[a - c as usize];
        }
    }
    ways[n]
}

solve :: Int -> [Int] -> Int
solve amount coins = foldl addCoin (1 : replicate amount 0) coins !! amount
  where
    -- with coin c allowed: new[a] = old[a] + new[a - c], built left to right
    addCoin old c = new
      where new = zipWith (+) old (replicate c 0 ++ new)

The same code is the reference solution to Ways to make an amount, where it is compiled and run against the tests in all six languages.

TimeO(coins · amount)

SpaceO(amount)

Swap the loops (amounts outside, coins inside) and the same code counts ordered sequences: the number of ways to climb a staircase with steps of the given sizes.