Burger Fervor, No While Loop

Hello, dynamic programming programmers,

Chapter 3 of Algorithmic Thinking is all about memoization and dynamic programming. I don’t know any other algorithm design technique that applies to so many problems and has such a dramatic impact on efficiency/speed. I’ll assume that you’ve already read through that chapter before reading this post.

At the start of the chapter, we solve the problem where Homer Simpson wants to spend as much time as possible eating burgers.

The way I chose to solve it in the book fills out the dynamic programming array – but then it has to use a while loop to identify the maximum time that can be completely filled with burgers.

Some readers have asked whether a version of the code can be written to avoid that while loop. That is, they want code that fills out the dynamic programming array and then finds the answer directly, with no post-processing loop. Can it be done?

Answer: yes! I didn’t do it this way in the book because I think it’s a little trickier, and does require using two parallel arrays. But it is pretty cool in its own right.

A New Solution

In this solution, we’ll use two dynamic programming arrays: time and burgers:

• time[i] answers the question: given i minutes, what is the maximum number of those minutes that can be spent eating burgers?
• burgers[i] answers the question: what is the maximum number of burgers that can be eaten in exactly time[i] minutes?

For example, suppose that we have 4-minute and 9-minute burgers. Then, time[15] will be 13 (the largest number of minutes up to 15 that can be spent eating burgers), and burgers[15] will be 2 (the largest number of burgers that can be eaten in exactly 13 minutes). Notice: we can’t let burgers[15] be 3 (three 4-minute burgers), because that would correspond to only 12 minutes (which is a worse solution than spending 13 minutes eating burgers).

The Code

Here’s my code implementing the above idea.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 10000

int max(int v1, int v2) {
  if (v1 > v2)
    return v1;
  else
    return v2;
}

void solve(int m, int n, int t) {
  int i, first, second;
  int time[SIZE];
  int burgers[SIZE];

  time[0] = 0;
  burgers[0] = 0;

  for (i = 1; i <= t; i++) {
    time[i] = 0;
    burgers[i] = 0;

    if (i >= m)
      first = time[i - m] + m;
    else
      first = -1;
    if (i >= n)
      second = time[i - n] + n;
    else
      second = -1;

    if (first > time[i] && first > second) {
      time[i] = first;
      burgers[i] = burgers[i - m] + 1;
    }
    else if (second > time[i] && second > first) {
      time[i] = second;
      burgers[i] = burgers[i - n] + 1;
    }
    else if (first > time[i] && first == second) {
      time[i] = first;
      burgers[i] = max(burgers[i - m], burgers[i - n]) + 1;
    }
  }

  if (time[t] == t)
    printf("%d\n", burgers[t]);
  else
    printf("%d %d\n", burgers[t], t - time[t]);
}

int main(void) {
  int m, n, t;
  while (scanf("%d%d%d", &m, &n, &t) != -1)
    solve(m, n, t);
  return 0;
}

On each iteration of the main for loop (22), there are three interesting possibilities:

• We can use the m-minute burger and it’s better than using the n-minute burger (35). In this case, we use the m-minute burger. In all cases, including this one, be careful to update both dynamic programming arrays (36-37).
• We can use the n-minute burger and it’s better than using the m-minute burger (39). In this case, we use the n-minute burger.
• Both types of burger can be used and they are equally good at filling up the time (43). In this case, we have a choice to make for the burgers array: we have to choose the burger that gives us the maximum burgers for this time (45).

With the two arrays filled out, we can move to outputting our answer. If the entire time can be filled with eating burgers (49), then we just print the number of burgers that can be eaten (50). Otherwise, we still print the number of burgers, but we also have to print the number of minutes spent drinking beer (52). To get this beer-drinking time, we take the total time t and subtract time[t] (the maximum time spent eating burgers).

An Incorrect Solution

It’s pretty easy to get the code wrong with this approach. Can you find test cases where the following code fails? Can you explain what goes wrong?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 10000

int max(int v1, int v2) {
  if (v1 > v2)
    return v1;
  else
    return v2;
}

void solve(int m, int n, int t) {
  int i, first, second;
  int time[SIZE];
  int burgers[SIZE];

  time[0] = 0;
  burgers[0] = 0;

  for (i = 1; i <= t; i++) {
    time[i] = 0;
    burgers[i] = 0;

    if (i >= m)
      first = time[i - m] + m;
    else
      first = -1;
    if (i >= n)
      second = time[i - n] + n;
    else
      second = -1;

    if (first > -1) {
      time[i] = first;
      burgers[i] = burgers[i - m] + 1;
    }
    if (second > -1) {
      time[i] = max(time[i], second);
      burgers[i] = max(burgers[i], burgers[i - n] + 1);
    }
  }

  if (time[t] == t)
    printf("%d\n", burgers[t]);
  else
    printf("%d %d\n", burgers[t], t - time[t]);
}

int main(void) {
  int m, n, t;
  while (scanf("%d%d%d", &m, &n, &t) != -1)
    solve(m, n, t);
  return 0;
}

Thank You!

This post here is directly inspired by reader questions. Keep them coming!

I also have a newsletter where I send occasional updates (like, very occasional… I have to get better at this). Please see my Contact and Newsletter page if you’d like to subscribe.