Hover Text:

General solutions get you a 50% tip.

Transcript

My Hobby:
Embedding NP-Complete problems in restaurant orders
[A menu is shown.]
Chotchkies Restaurant
Appetizers

  • Mixed Fruit 2.15
  • French Fries 2.75
  • Side Salad 3.35
  • Hot Wings 3.55
  • Mozzarella Sticks 4.20
  • Sampler Plate 5.80

Sandwiches

  • Barbecue 6.55

[Megan, another person, and Cueball are sitting at a table. Cueball is holding the menu as well as a thick book and is ordering from a waiter. Megan is facepalming.]
Cueball: We’d like exactly $15.05 worth of appetizers, please.
Waiter: …Exactly? Uhh…
Cueball: Here, these papers on the knapsack problem might help you out.
Waiter: Listen, I have six other tables to get to—
Cueball: —As fast as possible, of course. Want something on traveling salesman?

  • @200ok
    link
    510 months ago

    Thanks for sharing the xkcd explained link. That was interesting!

    SPOILER:

    !1. A combination of two orders of hot wings, one order of mixed fruit, and one sampler plate

    1. Seven mixed fruit orders (this solution was not intended - see trivia section in OP’s link)!<
    • @[email protected]
      link
      fedilink
      28 months ago

      You missed the greatest part:
      Randall explains […] that this was due to him using a Perl script with a bug (“You can’t compare IEEE floats for equality”).