Dynamic programming and recursion

Overlapping Subproblems

A problem has overlapping subproblems if finding its solution involves solving the same subproblem multiple times.

As an example, let’s look at the Fibonacci sequence (the series where each number is the sum of the two previous ones—0, 1, 1, 2, 3, 5, 8, …).

If we wanted to compute the nth Fibonacci number, we could use this simple recursive algorithm:

function fib(n) {
  if (n === 0 || n === 1) {
    return n;
  }
  return fib(n-1) + fib(n-2);
}
We’d call fib(n-1) and fib(n-2) subproblems of fib(n).

Now let’s look at what happens when we call fib(5):

Our function ends up recursively calling fib(2) three times. So the problem of finding the nth Fibonacci number has overlapping subproblems.

Memoization

Memoization ensures that a function doesn’t run for the same inputs more than once by keeping a record of the results for the given inputs (usually in an object).

For example, a simple recursive function for computing the th Fibonacci number:

function fib(n) {

  if (n < 0) {
    throw new Error(
      'Index was negative. No such thing as a negative index in a series.');
  }

  // Base cases
  if (n === 0 || n === 1) {
    return n;
  }

  console.log(`computing fib(${n})`);
  return fib(n - 1) + fib(n - 2);
}

Will run on the same inputs multiple times:

❯ fib(5)
  computing fib(5)
  computing fib(4)
  computing fib(3)
  computing fib(2)
  computing fib(2)
  computing fib(3)
  computing fib(2)
❮ 5

We can imagine the recursive calls of this function as a tree, where the two children of a node are the two recursive calls it makes. We can see that the tree quickly branches out of control:

To avoid the duplicate work caused by the branching, we can wrap the function in a class that stores an instance propertymemo, that maps inputs to outputs. Then we simply

  1. check memo to see if we can avoid computing the answer for any given input, and
  2. save the results of any calculations to memo.
class Fibber {
  constructor() {
    this.memo = {};
  }

  fib(n) {
    if (n < 0) {
      throw new Error('Index was negative. No such thing as a negative index in a series.');

    // Base cases
    } else if (n === 0 || n === 1) {
      return n;
    }

    // See if we've already calculated this
    if (this.memo.hasOwnProperty(n)) {
      console.log(`grabbing memo[${n}]`);
      return this.memo[n];
    }

    console.log(`computing fib(${n})`);
    const result = this.fib(n - 1) + this.fib(n - 2);

    // Memoize
    this.memo[n] = result;

    return result;
  }
}
We save a bunch of calls by checking the memo:
❯ new Fibber().fib(5)
  computing fib(5)
  computing fib(4)
  computing fib(3)
  computing fib(2)
  grabbing memo[2]
  grabbing memo[3]
❯ 5

Now in our recurrence tree, no node appears more than twice:

Memoization is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with the Fibonacci problem, above). The other common strategy for dynamic programming problems is going bottom-up, which is usually cleaner and often more efficient.

Bottom-Up Algorithms

Going bottom-up is a way to avoid recursion, saving the memory cost that recursion incurs when it builds up the call stack.

Put simply, a bottom-up algorithm “starts from the beginning,” while a recursive algorithm often “starts from the end and works backwards.”

For example, if we wanted to multiply all the numbers in the range 1..n, we could use this cute, top-down, recursive one-liner:

function product1ToN(n) {
  // We assume n >= 1
  return (n > 1) ? (n * product1ToN(n-1)) : 1;
}

This approach has a problem: it builds up a call stack of size O(n), which makes our total memory cost O(n). This makes it vulnerable to a stack overflow error, where the call stack gets too big and runs out of space.

To avoid this, we can instead go bottom-up:

function product1ToN(n) {
  // We assume n >= 1

  let result = 1;
  for (let num = 1; num <= n; num++) {
    result *= num;
  }

  return result;
}
This approach uses O(1) space (O(n) time).

Some compilers and interpreters will do what’s called tail call optimization (TCO), where it can optimize some recursive functions to avoid building up a tall call stack. Python and Java decidedly do not use TCO. Some Ruby implementations do, but most don’t. Some C implementations do, and the JavaScript spec recently allowed TCO. Scheme is one of the few languages that guarantee TCO in all implementations. In general, best not to assume your compiler/interpreter will do this work for you.

Going bottom-up is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with multiplying the numbers 1..n, above). The other common strategy for dynamic programming problems is memoization.

Practice
Question 1

Write a recursive function for generating all permutations of an input string. Return them as a set.

Don’t worry about time or space complexity—if we wanted efficiency we’d write an iterative version.

To start, assume every character in the input string is unique.

Your function can have loops—it just needs to also be recursive.

Do you have an answer? No?

Here is a hint to get you started:

Initial Breakdown

Let’s break the problem into subproblems. How could we re-phrase the problem of getting all permutations for “cats” in terms of a smaller but similar subproblem?

Think you have an answer now? Yes?

Then check your answer against this gotcha:

Gotchas

Make sure you have a base case!  Otherwise your function may never terminate!

Full Breakdown

Let’s break the problem into subproblems. How could we re-phrase the problem of getting all permutations for “cats” in terms of a smaller but similar subproblem?

Let’s make our subproblem be getting all permutations for all characters except the last one. If we had all permutations for “cat,” how could we use that to generate all permutations for “cats”?

We could put the “s” in each possible position for each possible permutation of “cat”!

These are our permutations of “cat”:

cat
cta
atc
act
tac
tca

For each of them, we add “s” in each possible position. So for “cat”:

cat
    scat
    csat
    cast
    cats

And for “cta”:

cta
    scta
    csta
    ctsa
    ctas

And so on.

Now that we can break the problem into subproblems, we just need a base case and we have a recursive algorithm!

Solution

If we’re making all permutations for “cat,” we take all permutations for “ca” and then put “t” in each possible position in each of those permutations. We use this approach recursively:

function getPermutations(string) {

  // Base case
  if (string.length <= 1) {
    return new Set([string]);
  }

  const allCharsExceptLast = string.slice(0, -1);
  const lastChar = string[string.length - 1];

  // Recursive call: get all possible permutations for all chars except last
  const permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);

  // Put the last char in all possible positions for each of the above permutations
  const permutations = new Set();
  permutationsOfAllCharsExceptLast.forEach(permutationOfAllCharsExceptLast => {
    for (let position = 0; position <= allCharsExceptLast.length; position++) {
      const permutation = permutationOfAllCharsExceptLast.slice(0, position) + lastChar + permutationOfAllCharsExceptLast.slice(position);
      permutations.add(permutation);
    }
  });

  return permutations;
}
Bonus

How does the problem change if the string can have duplicate characters?

What if we wanted to bring down the time and/or space costs?

What We Learned

This is one where playing with a sample input is huge. Sometimes it helps to think of algorithm design as a two-part process: first figure out how you would solve the problem “by hand,” as though the input was a stack of paper on a desk in front of you. Then translate that process into code.

Question 2

Write a function fib() that takes an integer  and returns the nth Fibonacci number.

Let’s say our Fibonacci series is 0-indexed and starts with 0. So:

fib(0);  // => 0
fib(1);  // => 1
fib(2);  // => 1
fib(3);  // => 2
fib(4);  // => 3
...
Do you have an answer? No?
Here is a hint to get you started:
Initial Breakdown

The nth Fibonacci number is defined in terms of the two previous Fibonacci numbers, so this seems to lend itself to recursion.

fib(n) = fib(n - 1) + fib(n - 2);
Can you write up a recursive solution? Yes?
Then check your answer against these gotchas one by one:
Gotchas

Our solution runs in nn time.

There’s a clever, more mathy solution that runs in  time, but we’ll leave that one as a bonus.

If you wrote a recursive function, think carefully about what it does. It might do repeat work, like computing fib(2) multiple times!

We can do this in O(1) space. If you wrote a recursive function, there might be a hidden space cost in the call stack! 

Full Breakdown

The nth Fibonacci number is defined in terms of the two previous Fibonacci numbers, so this seems to lend itself to recursion.

fib(n) = fib(n - 1) + fib(n - 2);

Can you write up a recursive solution?

As with any recursive function, we just need a base case and a recursive case:

  1. Base case:  is 0 or 1. Return .
  2. Recursive case: Return fib(n – 1) + fib(n – 2).
function fib(n) {
  if (n === 0 || n === 1) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

Okay, this’ll work! What’s our time complexity? It’s not super obvious. We might guess n, but that’s not quite right. Can you see why?

Each call to fib() makes two more calls. Let’s look at a specific example. Let’s say n=5If we call fib(5), how many calls do we make in total?

Try drawing it out as a tree where each call has two child calls, unless it’s a base case.

Here’s what the tree looks like:

We can notice this is a binary tree whose height is , which means the total number of nodes is O(2^n).

So our total runtime is O(2^n). That’s an “exponential time cost,” since the n is in an exponent. Exponential costs are terrible. This is way worse than O(n^2) or even O(n^(100)).

Our recurrence tree above essentially gets twice as big each time we add 1 to . So as  gets really big, our runtime quickly spirals out of control.

The craziness of our time cost comes from the fact that we’re doing so much repeat work. How can we avoid doing this repeat work?

We can memoize! 

Let’s wrap fib() in a class with an instance variable where we store the answer for any n that we compute:

class Fibber {
  constructor() {
    this.memo = {};
  }

  fib(n) {

    // Edge case: negative index
    if (n < 0) {
      throw new Error('Index was negative. No such thing as a negative index in a series.');
    }

    // Base case: 0 or 1
    else if (n === 0 || n === 1) {
      return n;
    }

    // See if we've already calculated this
    if (this.memo.hasOwnProperty(n)) {
      return this.memo[n];
    }

    const result = this.fib(n - 1) + this.fib(n - 2);

    // Memoize
    this.memo[n] = result;

    return result;
  }
}

What’s our time cost now?

Our recurrence tree will look like this:

The computer will build up a call stack with fib(5)fib(4)fib(3)fib(2)fib(1). Then we’ll start returning, and on the way back up our tree we’ll be able to compute each node’s 2nd call to fib() in constant time by just looking in the memo. n time in total.

What about space? memo takes up n space. Plus we’re still building up a call stack that’ll occupy n space. Can we avoid one or both of these space expenses?

Look again at that tree. Notice that to calculate fib(5) we worked “down” to fib(4)fib(3)fib(2), etc.

What if instead we started with fib(0) and fib(1) and worked “up” to n?

Solution

We use a bottom-up approach, starting with the 0th Fibonacci number and iteratively computing subsequent numbers until we get to n.

function fib(n) {

  // Edge cases:
  if (n < 0) {
    throw new Error('Index was negative. No such thing as a negative index in a series.');
  } else if (n === 0 || n === 1) {
    return n;
  }

  // We'll be building the fibonacci series from the bottom up
  // So we'll need to track the previous 2 numbers at each step
  let prevPrev = 0;  // 0th fibonacci
  let prev = 1;      // 1st fibonacci
  let current;       // Declare current

  for (let i = 1; i < n; i++) {

    // Iteration 1: current = 2nd fibonacci
    // Iteration 2: current = 3rd fibonacci
    // Iteration 3: current = 4th fibonacci
    // To get nth fibonacci ... do n-1 iterations.
    current = prev + prevPrev;
    prevPrev = prev;
    prev = current;
  }

  return current;
}
Complexity

 time and  space.

Bonus
    • If you’re good with matrix multiplication you can bring the time cost down even further, to . Can you figure out how?
What We Learned

This one’s a good illustration of the tradeoff we sometimes have between code cleanliness and efficiency.

We could use a cute, recursive function to solve the problem. But that would cost O(2^n) time as opposed to n time in our final bottom-up solution. Massive difference!

In general, whenever you have a recursive solution to a problem, think about what’s actually happening on the call stack. An iterative solution might be more efficient.

Question 3

Your quirky boss collects rare, old coins…

They found out you’re a programmer and asked you to solve something they’ve been wondering for a long time.

Write a function that, given:

  1. an amount of money
  2. an array of coin denominations

computes the number of ways to make the amount of money with coins of the available denominations.

Example: for amount=4 (4¢) and denominations=[1,2,3] (1¢, 2¢ and 3¢), your program would output 4—the number of ways to make 4¢ with those denominations:

  1. 1¢, 1¢, 1¢, 1¢
  2. 1¢, 1¢, 2¢
  3. 1¢, 3¢
  4. 2¢, 2¢

Do you have an answer? No?

Here is a hint to get you started:

Initial Breakdown

We need to find some way to break this problem down into subproblems.

Think you have an answer now? Yes?

Then check your answer against these gotchas one by one.

Gotchas

What if there’s no way to make the amount with the denominations? Does your function have reasonable behavior?

We can do this in  time and  space, where n is the amount of money and m is the number of denominations.

A simple recursive approach works, but you’ll find that your function gets called more than once with the same inputs. We can do better.

We could avoid the duplicate function calls by memoizing, but there’s a cleaner bottom-up approach.

Full Breakdown

We need to find some way to break this problem down into subproblems.

Here’s one way: for each denomination, we can use it once, or twice, or…as many times as it takes to reach or overshoot the amount with coins of that denomination alone.

For each of those choices of how many times to include coins of each denomination, we’re left with the subproblem of seeing how many ways we can get the remaining amount from the remaining denominations.

Here’s that approach in pseudocode:

function numberOfWays(amount, denominations) {
  let answer = 0;
  denominations.forEach(denomination => {
    possibleNumTimesToUseDenominationWithoutOvershootingAmount.forEach(numTimesToUseDenomination => {
      answer += numberOfWays(amountRemaining, otherDenominations);
    });
  });
  return answer;
}

The answer for some of those subproblems will of course be 0. For example, there’s no way to get 1¢ with only 2¢ coins.

As a recursive function, we could formalize this as:

function changePossibilitiesTopDown(amountLeft, denominations, currentIndex = 0) {

  // Base cases:
  // We hit the amount spot on. yes!
  if (amountLeft === 0) return 1;

  // We overshot the amount left (used too many coins)
  if (amountLeft < 0) return 0;

  // We're out of denominations
  if (currentIndex === denominations.length) return 0;

  console.log('checking ways to make ' + amountLeft + ' with [' + denominations.slice(currentIndex).join(', ') + ']');

  // Choose a current coin
  const currentCoin = denominations[currentIndex];

  // See how many possibilities we can get
  // for each number of times to use currentCoin
  let numPossibilities = 0;
  while (amountLeft >= 0) {
    numPossibilities += changePossibilitiesTopDown(amountLeft, denominations, currentIndex + 1);
    amountLeft -= currentCoin;
  }

  return numPossibilities;
}
But there’s a problem—we’ll often duplicate the work of checking remaining change possibilities. Note the duplicate calls with the input 4, [1,2,3]:
❯ changePossibilitiesTopDown(4, [1, 2, 3]);
  checking ways to make 4 with [1, 2, 3]
  checking ways to make 4 with [2, 3]
  checking ways to make 4 with [3]
  checking ways to make 2 with [3]
  checking ways to make 3 with [2, 3]
  checking ways to make 3 with [3]
  checking ways to make 1 with [3]
  checking ways to make 2 with [2, 3]
  checking ways to make 2 with [3]
  checking ways to make 1 with [2, 3]
  checking ways to make 1 with [3]
❮ 4

For example, we check ways to make 2 with [3] twice.

We can do better. How do we avoid this duplicate work and bring down the time cost?

One way is to memoize. 

Here’s what the memoization might look like:

class Change {
  constructor() {
    this.memo = {};
  }

  changePossibilitiesTopDown(amountLeft, denominations, currentIndex = 0) {

    // Check our memo and short-circuit if we've already solved this one
    const memoKey = [amountLeft, currentIndex].join(', ');
    if (this.memo.hasOwnProperty(memoKey)) {
      console.log('grabbing memo [' + memoKey + ']');
      return this.memo[memoKey];
    }

    // Base cases:
    // We hit the amount spot on. yes!
    if (amountLeft === 0) return 1;

    // We overshot the amount left (used too many coins)
    if (amountLeft < 0) return 0;

    // We're out of denominations
    if (currentIndex === denominations.length) return 0;

    console.log('checking ways to make ' + amountLeft + ' with [' + denominations.slice(currentIndex).join(', ') + ']');

    // Choose a current coin
    const currentCoin = denominations[currentIndex];

    // See how many possibilities we can get
    // for each number of times to use currentCoin
    let numPossibilities = 0;
    while (amountLeft >= 0) {
      numPossibilities += this.changePossibilitiesTopDown(amountLeft, denominations, currentIndex + 1);
      amountLeft -= currentCoin;
    }

    // Save the answer in our memo so we don't compute it again
    this.memo[memoKey] = numPossibilities;
    return numPossibilities;
  }
}
And now our checking has no duplication:
❯ new Change().changePossibilitiesTopDown(4, [1, 2, 3]);
  checking ways to make 4 with [1, 2, 3]
  checking ways to make 4 with [2, 3]
  checking ways to make 4 with [3]
  checking ways to make 2 with [3]
  checking ways to make 3 with [2, 3]
  checking ways to make 3 with [3]
  checking ways to make 1 with [3]
  checking ways to make 2 with [2, 3]
  grabbing memo [2, 2]
  checking ways to make 1 with [2, 3]
  grabbing memo [1, 2]
❮ 4

This answer is quite good. It certainly solves our duplicate work problem. It takes  time and  space, where n is the size of amount and m is the number of items in denominations(Except we’d need to remove the line where we log “checking ways to make…” because making all those subarrays will take O(m^2) space!)

However, we can do better. Because our method is recursive it will build up a large call stack  of size O(m). Of course, this cost is eclipsed by the memory cost of memo, which is . But it’s still best to avoid building up a large stack like this, because it can cause a stack overflow (yes, that means recursion is usually better to avoid for functions that might have arbitrarily large inputs).

It turns out we can get  additional space.

A great way to avoid recursion is to go bottom-up. 

Our recursive approach was top-down because it started with the final value for amount and recursively broke the problem down into subproblems with smaller values for amount. What if instead we tried to compute the answer for small values of amount first, and use those answers to iteratively compute the answer for higher values until arriving at the final amount?

We can start by making an array waysOfDoingNCents, where the index is the amount and the value at each index is the number of ways of getting that amount.

This array will take O(n) space, where n is the size of amount.

To further simplify the problem, we can work with only the first coin in denominations, then add in the second coin, then the third, etc.

What would waysOfDoingNCents look like for just our first coin: 1¢? Let’s call this waysOfDoingNCents1.

const waysOfDoingNCents1 = [
  1,  // 0c:  No coins
  1,  // 1c:  1 1c coin
  1,  // 2c:  2 1c coins
  1,  // 3c:  3 1c coins
  1,  // 4c:  4 1c coins
  1,  // 5c:  5 1c coins
];
Now what if we add a 2¢ coin?
const waysOfDoingNCents1And2 = [
  1,      // 0c:  No change
  1,      // 1c:  No change
  1 + 1,  // 2c:  New [(2)]
  1 + 1,  // 3c:  New [(2, 1)]
  1 + 2,  // 4c:  New [(2, 1, 1), (2,2)]
  1 + 2,  // 5c:  New [(2, 1, 1, 1), (2, 2, 1)]
];

How do we formalize this process of going from waysOfDoingNCents1 to waysOfDoingNCents1And2?

Let’s suppose we’re partway through already (this is a classic dynamic programming approach). Say we’re trying to calculate waysOfDoingNCents1And2[5]. Because we’re going bottom-up, we know we already have:

  1. waysOfDoingNCents1And2 for amounts less than 5
  2. a fully-populated waysOfDoingNCents1

So how many new ways should we add to waysOfDoingNCents1[5] to get waysOfDoingNCents1And2[5]?

Well, if there are any new ways to get 5¢ now that we have 2¢ coins, those new ways must involve at least one 2¢ coin. So if we presuppose that we’ll use one 2¢ coin, that leaves us with 5-2=3 left to come up with. We already know how many ways we can get 3¢ with 1¢ and 2¢ coins: waysOfDoingNCents1And2[3], which is 2.

So we can see that:

waysOfDoingNCents1And2[5] = waysOfDoingNCents1[5] + waysOfDoingNCents1And2[5 - 2]

Why don’t we also need to check waysOfDoingNCents1And2[5 – 2 – 2] (two 2¢ coins)? Because we already checked waysOfDoingNCents1And2[1] when calculating waysOfDoingNCents1And2[3]. We’d be counting some arrangements multiple times. In other words, waysOfDoingNCents1And2[k] already includes the full count of possibilities for getting k, including possibilities that use 2¢ any number of times. We’re only interested in how many more possibilities we might get when we go from k to k+2 and thus have the ability to add one more 2¢ coin to each of the possibilities we have for k.

Solution

We use a bottom-up algorithm to build up a table waysOfDoingNCents such that waysOfDoingNCents[k] is how many ways we can get to k cents using our denominations. We start with the base case that there’s one way to create the amount zero, and progressively add each of our denominations.

The number of new ways we can make a higherAmount when we account for a new coin is simply waysOfDoingNCents[higherAmount – coin], where we know that value already includes combinations involving coin (because we went bottom-up, we know smaller values have already been calculated).

function changePossibilitiesBottomUp(amount, denominations) {

  // Initialize an array of zeros with indices up to amount
  const waysOfDoingNcents = new Array(amount + 1).fill(0);
  waysOfDoingNcents[0] = 1;

  denominations.forEach(coin => {
    for (let higherAmount = coin; higherAmount <= amount; higherAmount++) {
      const higherAmountRemainder = higherAmount - coin;
      waysOfDoingNcents[higherAmount] += waysOfDoingNcents[higherAmountRemainder];
    }
  });

  return waysOfDoingNcents[amount];
}

Here’s how waysOfDoingNCents would look in successive iterations of our function for amount=5 and denominations=[1,3,5].

===========
key:
a = higherAmount
r = higherAmountRemainder
===========

============
for coin = 1:
============
[1, 1, 0, 0, 0, 0]
 r  a

[1, 1, 1, 0, 0, 0]
    r  a

[1, 1, 1, 1, 0, 0]
       r  a

[1, 1, 1, 1, 1, 0]
          r  a

[1, 1, 1, 1, 1, 1]
             r  a

============
for coin = 3:
=============
[1, 1, 1, 2, 1, 1]
 r        a

[1, 1, 1, 2, 2, 1]
    r        a

[1, 1, 1, 2, 2, 2]
       r        a

============
for coin = 5:
=============
[1, 1, 1, 2, 2, 3]
 r              a


final answer: 3
Complexity

 time and O(n) additional space, where n is the amount of money and m is the number of potential denominations.

What We Learned

This question is in a broad class called “dynamic programming.” We have a bunch more dynamic programming questions we’ll go over later.

Dynamic programming is kind of like the next step up from greedy. You’re taking that idea of “keeping track of what we need in order to update the best answer so far,” and applying it to situations where the new best answer so far might not just have to do with the previous answer, but some other earlier answer as well.

So as you can see in this problem, we kept track of all of our previous answers to smaller versions of the problem (called “subproblems”) in a big array called waysOfDoingNCents.

Again, same idea of keeping track of what we need in order to update the answer as we go, like we did when storing the max product of 2, min product of 2, etc in the highest product of 3 questions. Except now the thing we need to keep track of is all our previous answers, which we’re keeping in an array.

We built that array bottom-up, but we also talked about how we could do it top-down and memoize. Going bottom-up is cleaner and usually more efficient, but often it’s easier to think of the top-down version first and try to adapt from there.

Dynamic programming is a weak point for lots of candidates. If this one was tricky for you, don’t fret. We have more coming later.

Question 4

You are a renowned thief who has recently switched from stealing precious metals to stealing cakes because of the insane profit margins. You end up hitting the jackpot, breaking into the world’s largest privately-owned stock of cakes—the vault of the Queen of England.

While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.

Each type of cake has a weight and a value, stored in an object with two properties:

  1. weight: the weight of the cake in kilograms
  2. value: the monetary value of the cake in British shillings

For example:

// Weighs 7 kilograms and has a value of 160 shillings
{ weight: 7, value: 160 }

// Weighs 3 kilograms and has a value of 90 shillings
{ weight: 3, value: 90 }

You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.

Write a function maxDuffelBagValue() that takes an array of cake type objectand a weight capacity, and returns the maximum monetary value the duffel bag can hold.

For example:

const cakeTypes = [
  { weight: 7, value: 160 },
  { weight: 3, value: 90 },
  { weight: 2, value: 15 },
];

const capacity = 20;

maxDuffelBagValue(cakeTypes, capacity);
// Returns 555 (6 of the middle type of cake and 1 of the last type of cake)

Weights and values may be any non-negative integer. Yes, it’s weird to think about cakes that weigh nothing or duffel bags that can’t hold anything. But we’re not just super mastermind criminals—we’re also meticulous about keeping our algorithms flexible and comprehensive.

Do you have an answer? No?

Here is a hint to get you started:

Initial Breakdown

The brute force approach is to try every combination of cakes, but that would take a really long time—you’d surely be captured.

What if we just look at the cake with the highest value?

Think you have an answer now? Yes?

Then check your answer against these gotchas one at a time.

Gotchas

Does your function work if the duffel bag’s weight capacity is 0 kg?

Does your function work if any of the cakes weigh 0 kg? Think about a cake whose weight and value are both 0.

We can do this in  time and  space, where n is the number of types of cakes and k is the duffel bag’s capacity!

Full Breakdown

The brute force approach is to try every combination of cakes, but that would take a really long time—you’d surely be captured.

What if we just look at the cake with the highest value?

We could keep putting the cake with the highest value into our duffel bag until adding one more would go over our weight capacity. Then we could look at the cake with the second highest value, and so on until we find a cake that’s not too heavy to add.

Will this work?

Nope. Let’s say our capacity is 100 kg and these are our two cakes:

{ weight: 1,  value: 30 }
{ weight: 50, value: 200 }

With our approach, we’ll put in two of the second type of cake for a total value of 400 shillings. But we could have put in a hundred of the first type of cake, for a total value of 3000 shillings!

Just looking at the cake’s values won’t work. Can we improve our approach?

Well, why didn’t it work?

We didn’t think about the weight! How can we factor that in?

What if instead of looking at the value of the cakes, we looked at their value/weight ratio? Here are our example cakes again:

{ weight: 1,  value: 30 }
{ weight: 50, value: 200 }

The second cake has a higher value, but look at the value per kilogram.

The second type of cake is worth 4 shillings/kg (200/50), but the first type of cake is worth 30 shillings/kg (30/1)!

Ok, can we just change our algorithm to use the highest value/weight ratio instead of the highest value? We know it would work in our example above, but try some more tests to be safe.

We might run into problems if the weight of the cake with the highest value/weight ratio doesn’t fit evenly into the capacity. Say we have these two cakes:

{ weight: 3, value: 40 }
{ weight: 5, value: 70 }

If our capacity is 8 kg, no problem. Our algorithm chooses one of each cake, giving us a haul worth 110 shillings, which is optimal.

But if the capacity is 9 kg, we’re in trouble. Our algorithm will again choose one of each cake, for a total value of 110 shillings. But the actual optimal value is 120 shillings—three of the first type of cake!

So even looking at the value/weight ratios doesn’t always give us the optimal answer!

Let’s step back. How can we ensure we get the optimal value we can carry?

Try thinking small. How can we calculate the maximum value for a duffel bag with a weight capacity of 1 kg? (Remember, all our weights and values are integers.)

If the capacity is 1 kg, we’ll only care about cakes that weigh 1 kg (for simplicity, let’s ignore zeroes for now). And we’d just want the one with the highest value.

We could go through every cake, using a greedy  approach to keep track of the max value we’ve seen so far.

Here’s an example solution:

function maxDuffelBagValueWithCapacity1(cakeTypes) {

  let maxValueAtCapacity1 = 0;

  cakeTypes.forEach(cakeType => {

    if (cakeType.weight === 1) {
      maxValueAtCapacity1 = Math.max(maxValueAtCapacity1, cakeType.value);
    }
  });

  return maxValueAtCapacity1;
}
Ok, now what if the capacity is 2 kg? We’ll need to be a bit more clever.

It’s pretty similar. Again we’ll track a max value, let’s say with a variable maxValueAtCapacity2. But now we care about cakes that weigh 1 or 2 kg. What do we do with each cake? And keep in mind, we can lean on the code we used to get the max value at weight capacity 1 kg.

  1. If the cake weighs 2 kg, it would fill up our whole capacity if we just took one. So we just need to see if the cake’s value is higher than our current maxValueAtCapacity2.
  2. If the cake weighs 1 kg, we could take one, and we’d still have 1 kg of capacity left. How do we know the best way to fill that extra capacity? We can use the max value at capacity 1. We’ll see if adding the cake’s value to the max value at capacity 1 is better than our current maxValueAtCapacity2.

Does this apply more generally? If we can use the max value at capacity 1 to get the max value at capacity 2, can we use the max values at capacity 1 and 2 to get the max value at capacity 3?

Looks like this problem might have overlapping subproblems! 

Let’s see if we can build up to the given weight capacity, one capacity at a time, using the max values from previous capacities. How can we do this?

Well, let’s try one more weight capacity by hand—3 kg. So we already know the max values at capacities 1 and 2. And just like we did with maxValueAtCapacity1 and maxValueAtCapacity2, now we’ll track maxValueAtCapacity3 and loop through every cake:

let maxValueAtCapacity3 = 0;

cakeTypes.forEach(cakeType => {
  // Only care about cakes that weigh 3 kg or less
  ...
});

What do we do for each cake?

If the current cake weighs 3 kg, easy—we see if it’s more valuable than our current maxValueAtCapacity3.

What if the current cake weighs 2 kg?

Well, let’s see what our max value would be if we used the cake. How can we calculate that?

If we include the current cake, we can only carry 1 more kilogram. What would be the max value we can carry?

We already know the maxValueAtCapacity1! We can just add that to the current cake’s value!

Now we can see which is higher—our current maxValueAtCapacity3, or the new max value if we use the cake:

const maxValueUsingCake = maxValueAtCapacity1 + cakeType.value;
maxValueAtCapacity3 = Math.max(maxValueAtCapacity3, maxValueUsingCake);

Finally, what if the current cake weighs 1 kg?

Basically, the same as if it weighs 2 kg:

const maxValueUsingCake = maxValueAtCapacity2 + cakeType.value;
maxValueAtCapacity3 = Math.max(maxValueAtCapacity3, maxValueUsingCake);

There’s gotta be a pattern here. We can keep building up to higher and higher capacities until we reach our input capacity. Because the max value we can carry at each capacity is calculated using the max values at previous capacities, we’ll need to solve the max value for every capacity from 0 up to our duffel bag’s actual weight capacity.

Can we write a function to handle all the capacities?

To start, we’ll need a way to store and update all the max monetary values for each capacity.

We could use an object, where the keys represent capacities and the values represent the max possible monetary values at those capacities. Objects are built on arrays, so we can save some overhead by just using an array.

function maxDuffelBagValue(cakeTypes, weightCapacity) {

  // Array to hold the maximum possible value at every
  // integer capacity from 0 to weightCapacity
  // starting each index with value 0
  const maxValuesAtCapacities = new Array(weightCapacity + 1).fill(0);
}

What do we do next? We’ll need to work with every capacity up to the input weight capacity. That’s an easy loop:

// Every integer from 0 to the input weightCapacity
for (let currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) {
  ...
}

What will we do inside this loop? This is where it gets a little tricky.

We care about any cakes that weigh the current capacity or less. Let’s try putting each cake in the bag and seeing how valuable of a haul we could fit from there.

So we’ll write a loop through all the cakes (ignoring cakes that are too heavy to fit):

cakeTypes.forEach(cakeType => {

  // If the cake weighs as much or less than the current capacity
  // see what our max value could be if we took it!
  if (cakeType.weight <= currentCapacity) {
    // Find maxValueUsingCake
    ...
  }
});
And put it in our function body so far:
function maxDuffelBagValue(cakeTypes, weightCapacity) {

  // We make an array to hold the maximum possible value at every
  // duffel bag weight capacity from 0 to weightCapacity
  // starting each index with value 0
  const maxValuesAtCapacities = new Array(weightCapacity + 1).fill(0);

  for (let currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) {

    cakeTypes.forEach(cakeType => {

      // If the cake weighs as much or less than the current capacity
      // See what our max value could be if we took it!
      if (cakeType.weight <= currentCapacity) {
        // Find maxValueUsingCake
        ...
      }
    });
  }
}

How do we compute maxValueUsingCake?

Remember when we were calculating the max value at capacity 3kg and we “hard-coded” the maxValueUsingCake for cakes that weigh 3 kg, 2kg, and 1kg?

// Cake weighs 3 kg
const maxValueUsingCake = cakeType.value;

// Cake weighs 2 kg
const maxValueUsingCake = maxValueAtCapacity1 + cakeType.value;

// Cake weighs 1 kg
const maxValueUsingCake = maxValueAtCapacity2 + cakeType.value;

How can we generalize this? With our new function body, look at the variables we have in scope:

  1. maxValuesAtCapacities
  2. currentCapacity
  3. cakeType

Can we use these to get maxValueUsingCake for any cake?

Well, let’s figure out how much space would be left in the duffel bag after putting the cake in:

const remainingCapacityAfterTakingCake = currentCapacity - cakeType.weight;

So maxValueUsingCake is:

  1. the current cake’s value, plus
  2. the best value we can fill the remainingCapacityAfterTakingCake with
const remainingCapacityAfterTakingCake = currentCapacity - cakeType.weight;
const maxValueUsingCake = cakeType.value + maxValuesAtCapacities[remainingCapacityAfterTakingCake];

We can squish this into one line:

const maxValueUsingCake = cakeType.value + maxValuesAtCapacities[currentCapacity - cakeType.weight];

Since remainingCapacityAfterTakingCake is a lower capacity, we’ll have always already computed its max value and stored it in our maxValuesAtCapacities!

Now that we know the max value if we include the cakeshould we include it? How do we know?

Let’s allocate a variable currentMaxValue that holds the highest value we can carry at the current capacity. We can start it at zero, and as we go through all the cakes, any time the value using a cake is higher than currentMaxValue, we’ll update currentMaxValue!

currentMaxValue = Math.max(maxValueUsingCake, currentMaxValue);

What do we do with each value for currentMaxValue? What do we need to do for each capacity when we finish looping through all the cakes?

We save each currentMaxValue in the maxValuesAtCapacities array. We’ll also need to make sure we set currentMaxValue to zero in the right place in our loops—we want it to reset every time we start a new capacity.

So here’s our function so far:

function maxDuffelBagValue(cakeTypes, weightCapacity) {

  // We make an array to hold the maximum possible value at every
  // duffel bag weight capacity from 0 to weightCapacity
  // starting each index with value 0
  const maxValuesAtCapacities = new Array(weightCapacity + 1).fill(0);

  for (let currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) {

    // Set a variable to hold the max monetary value so far for currentCapacity
    let currentMaxValue = 0;

    cakeTypes.forEach(cakeType => {

      // If the current cake weighs as much or less than the current weight capacity
      // it's possible taking the cake would get a better value
      if (cakeType.weight <= currentCapacity) {

        // So we check: should we use the cake or not?
        // If we use the cake, the most kilograms we can include in addition to the cake
        // We're adding is the current capacity minus the cake's weight. we find the max
        // value at that integer capacity in our array maxValuesAtCapacities
        const maxValueUsingCake = cakeType.value
          + maxValuesAtCapacities[currentCapacity - cakeType.weight];

        // Now we see if it's worth taking the cake. how does the
        // value with the cake compare to the currentMaxValue?
        currentMaxValue = Math.max(maxValueUsingCake, currentMaxValue);
      }
    });

    // Add each capacity's max value to our array so we can use them
    // when calculating all the remaining capacities
    maxValuesAtCapacities[currentCapacity] = currentMaxValue;
  }
}

Looking good! But what’s our final answer?

Our final answer is maxValuesAtCapacities[weightCapacity]!

Okay, this seems complete. What about edge cases?

Remember, weights and values can be any non-negative integer. What about zeroes? How can we handle duffel bags that can’t hold anything and cakes that weigh nothing?

Well, if our duffel bag can’t hold anything, we can just return 0. And if a cake weighs 0 kg, we return infinity. Right?

Not that simple!

What if our duffel bag holds 0 kg, and we have a cake that weighs 0 kg. What do we return?

And what if we have a cake that weighs 0 kg, but its value is also 0. If we have other cakes with positive weights and values, what do we return?

If a cake’s weight and value are both 0, it’s reasonable to not have that cake affect what we return at all.

If we have a cake that weighs 0 kg and has a positive value, it’s reasonable to return infinity, even if the capacity is 0.

For returning infinity, we have several choices. We could return:

  1. The JavaScript Infinity property.
  2. Return a custom response, like the string ‘infinity’.
  3. Raise an exception indicating the answer is infinity.

What are the advantages and disadvantages of each option?

For the first option the advantage is we get the behavior of infinity. Compared to any other integer, Infinity will be greater. And it’s a number, which can be an advantage or disadvantage—we might want our result to always be the same type, but without manually checking we won’t know if we mean an actual value or the special case of infinity.

For the second option the advantage is we can create a custom behavior that we—or our function‘s users—could know to expect. The disadvantage is we’d have to explicitly check for that behavior, otherwise we might end up trying to parse the string “infinity” as an integer, which could give us an error or (perhaps worse) a random number. In a production system, a function that sometimes returns an integer and sometimes returns a string would probably be seen as sloppy.

The third option is a good choice if we decide infinity is usually an “unacceptable” answer. For example, we might decide an infinite answer means we’ve probably entered our inputs wrong. Then, if we really wanted to “accept” an infinite answer, we could always “catch” this exception when we call our function.

Any option could be reasonable. We’ll go with the first one here.

Solution

This is a classic computer science puzzle called “the unbounded knapsack problem.”

We use a bottom-up approach to find the max value at our duffel bag’s weightCapacity by finding the max value at every capacity from 0 to weightCapacity.

We allocate an array maxValuesAtCapacities where the indices are capacities and each value is the max value at that capacity.

For each capacity, we want to know the max monetary value we can carry. To figure that out, we go through each cake, checking to see if we should take that cake.

The best monetary value we can get if we take a given cake is simply:

  1. that cake’s value, plus
  2. the best monetary value we can carry in our remaining duffel bag capacity after taking the cake—which we’ll already have stored in maxValuesAtCapacities

To handle weights and values of zero, we return infinity only if a cake weighs nothing and has a positive value.

function maxDuffelBagValue(cakeTypes, weightCapacity) {

  // We make an array to hold the maximum possible value at every
  // duffel bag weight capacity from 0 to weightCapacity
  // starting each index with value 0
  const maxValuesAtCapacities = new Array(weightCapacity + 1).fill(0);

  for (let currentCapacity = 0; currentCapacity <= weightCapacity; currentCapacity++) {

    // Set a variable to hold the max monetary value so far for currentCapacity
    let currentMaxValue = 0;

    // We use a for loop here instead of forEach because we return infinity
    // If we get a cakeType that weighs nothing and has a value. but forEach
    // loops always return undefined and you can't break out of them without
    // throwing an exception
    for (let j = 0; j < cakeTypes.length; j++) {
      const cakeType = cakeTypes[j];

      // If a cake weighs 0 and has a positive value the value of our duffel bag is infinite!
      if (cakeType.weight === 0 && cakeType.value !== 0) {
        return Infinity;
      }

      // If the current cake weighs as much or less than the current weight capacity
      // it's possible taking the cake would get a better value
      if (cakeType.weight <= currentCapacity) {

        // So we check: should we use the cake or not?
        // If we use the cake, the most kilograms we can include in addition to the cake
        // We're adding is the current capacity minus the cake's weight. we find the max
        // value at that integer capacity in our array maxValuesAtCapacities
        const maxValueUsingCake = cakeType.value
          + maxValuesAtCapacities[currentCapacity - cakeType.weight];

        // Now we see if it's worth taking the cake. how does the
        // value with the cake compare to the currentMaxValue?
        currentMaxValue = Math.max(maxValueUsingCake, currentMaxValue);
      }
    }

    // Add each capacity's max value to our array so we can use them
    // when calculating all the remaining capacities
    maxValuesAtCapacities[currentCapacity] = currentMaxValue;
  }

  return maxValuesAtCapacities[weightCapacity];
}
Complexity

 time, and  space, where  is number of types of cake and k is the capacity of the duffel bag. We loop through each cake (n cakes) for every capacity (k capacities), so our runtime is , and maintaining the array of  capacities gives us the O(k) space.

Congratulations! Because of dynamic programming, you have successfully stolen the Queen’s cakes and made it big.

Keep in mind: in some cases, it might not be worth using our optimal dynamic programming solution. It’s a pretty slow algorithm—without any context (not knowing how many cake types we have, what our weight capacity is, or just how they compare) it’s easy to see  growing out of control quickly if  or  is large.

If we cared about time, like if there was an alarm in the vault and we had to move quickly, it might be worth using a faster algorithm that gives us a good answer, even if it’s not always the optimal answer. Some of our first ideas in the breakdown were to look at cake values or value/weight ratios. Those algorithms would probably be faster, taking  time (we’d have to start by sorting the input).

Sometimes an efficient, good answer might be more practical than an inefficient, optimal answer.

Bonus
  1. We know the max value we can carry, but which cakes should we take, and how many? Try adjusting your answer to return this information as well.
  2. What if we check to see if all the cake weights have a common denominator? Can we improve our algorithm?
  3. A cake that’s both heavier and worth less than another cake would never be in the optimal solution. This idea is called dominance relations. Can you apply this idea to save some time? Hint: dominance relations can apply to sets of cakes, not just individual cakes.
  4. What if we had an object for every individual cake instead of types of cakes? So now there’s not an unlimited supply of a type of cake—there’s exactly one of each. This is a similar but harder problem, known as the 0/1 Knapsack problem.
What We Learned

This question is our spin on the famous “unbounded knapsack problem”—a classic dynamic programming question.