Difference between revisions of "287: NP-Complete"
(page created as stub) |
|||
| Line 12: | Line 12: | ||
== Description == | == Description == | ||
| + | Another entry in the “My Hobby” series of cartoons; here, Cueball is embedding NP-complete problems in restaurant orders. Specifically, he is ordering appetizers not by explicitly stating the names of the appetizers, but by the total price of the chosen appetizers. This is a (simplified) example of the knapsack problem. The [[wikipedia:Knapsack_problem|knapsack]] (or rucksack) problem is a problem in combinatorial optimization, as follows: if you have a knapsack (or backpack, or rucksack, as your regional desire to call it may be) which can hold a specific amount of weight, and you have a set of items, each with its own assigned value and weight, can you select items to put into the knapsack so that (1) the weight does not exceed the capacity of the knapsack, and (2) the combined value of all the items is maximized. (The example in this cartoon is simplified, because we are not given the corresponding “value” of each item – like we would be if, for example, Cueball and his two friends assigned a perceived value of 7 on a scale of 1 to 10 for getting hot wings, but only a 2 out of 10 for a side salad. Another way to introduce complexity into the problem would be if the patrons were considering the calorie values of each appetizer on the menu.) | ||
== Solution == | == Solution == | ||
| + | There are exactly two solutions to the problem posed in the comic strip, combinations of appetizers which total $15.05: either (1) seven mixed fruit orders, or (2) a combination of two orders of hot wings, one order of mixed fruit, and one sampler plate. | ||
[[Category:My Hobby]] | [[Category:My Hobby]] | ||
Revision as of 19:22, 7 August 2012
| NP-Complete |
 Title text: General solutions get you a 50% tip. |
Image Text
General solutions get you a 50% tip.
Description
Another entry in the “My Hobby” series of cartoons; here, Cueball is embedding NP-complete problems in restaurant orders. Specifically, he is ordering appetizers not by explicitly stating the names of the appetizers, but by the total price of the chosen appetizers. This is a (simplified) example of the knapsack problem. The knapsack (or rucksack) problem is a problem in combinatorial optimization, as follows: if you have a knapsack (or backpack, or rucksack, as your regional desire to call it may be) which can hold a specific amount of weight, and you have a set of items, each with its own assigned value and weight, can you select items to put into the knapsack so that (1) the weight does not exceed the capacity of the knapsack, and (2) the combined value of all the items is maximized. (The example in this cartoon is simplified, because we are not given the corresponding “value” of each item – like we would be if, for example, Cueball and his two friends assigned a perceived value of 7 on a scale of 1 to 10 for getting hot wings, but only a 2 out of 10 for a side salad. Another way to introduce complexity into the problem would be if the patrons were considering the calorie values of each appetizer on the menu.)
Solution
There are exactly two solutions to the problem posed in the comic strip, combinations of appetizers which total $15.05: either (1) seven mixed fruit orders, or (2) a combination of two orders of hot wings, one order of mixed fruit, and one sampler plate.
