#287: NP-Complete explain

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?