# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## Saturday, June 13, 2009

### XKCD Knapsack Solution

A brute force solution to the following comic from href="http://xkcd.com/287/">XKCD:

title="General solutions get you a 50% tip."
src="http://imgs.xkcd.com/comics/np_complete.png">

Assuming the one sandwich represents the end of the menu, I used an
exhaustive search algorithm. Things to note are the use of zip(*table)
to transpose the items and itertools.product instead of nested for
loops.

`'''from:  href="http://xkcd.com/287/">http://xkcd.com/287/''' color="#a020f0">from itertools  color="#a020f0">import productitems = ( (' color="#ff00ff">MIXED FRUIT',   2.15),          (' color="#ff00ff">FRENCH FRIES',  2.75),          (' color="#ff00ff">SIDE SALAD',    3.35),          (' color="#ff00ff">HOT WINGS',     3.55),          (' color="#ff00ff">MOZZ STICKS',   4.20),          (' color="#ff00ff">SAMPLER PLATE', 5.80),          (' color="#ff00ff">BARBEQUE',      6.55) )exactcost = 15.05dishes, prices = zip(*items)rangeofdishes = [tuple(range(1+int( (exactcost+0.005)/price )))  color="#804040">for price  color="#804040">in prices]possibleorders = [tuple(zip(dishes, numbers))                   color="#804040">for numbers  color="#804040">in product(*rangeofdishes)                   color="#804040">if int(exactcost*100)                       == int(100* sum(num*price                                        color="#804040">for num,price  color="#804040">in zip(numbers, prices)))                  ] color="#804040">print(' color="#6a5acd">\nALL POSSIBLE CHOICES OF MENU ITEMS THAT COST %.2f, ONE PER LINE' % exactcost) color="#804040">for order  color="#804040">in possibleorders:     color="#804040">print( ' color="#ff00ff">  ',           ' color="#ff00ff">, '.join(' color="#ff00ff">%s: %i' % dishcount  color="#804040">for dishcount  color="#804040">in order  color="#804040">if dishcount[1]))`

style="font-family: monospace;">ALL POSSIBLE CHOICES OF MENU
ITEMS THAT COST 15.05, ONE PER LINE style="font-family: monospace;">

MIXED FRUIT: 1, HOT WINGS: 2, SAMPLER PLATE: 1
style="font-family: monospace;">

MIXED FRUIT: 2, MOZZ STICKS: 1, BARBEQUE: 1

MIXED FRUIT: 7

(I'd go with the hot wings).

1. I don't think the BBQ sandwich was supposed to be in there, it's not an appetizer. So #2 isn't valid. :)

2. Laughing out loud.

3. If BBQ as an appetizer is wrong, I don't want to be right.

4. Seeing as I used barbeque as an appetizer I think I need t justify it: Sandwiches are indented w.r.t. the sampler plate so is read as a sub-section of the appetizers ;-)

(Let the battle commence).

5. Since it is cut off on the menu maybe half a BBQ qualifies.

6. Yo momma never told you not to use floating-point for currency calculations?

7. You leave my mother out of this!

You will note however the gentle sprinkling of 'int' and half cent fairy dust to appease the floating point approximation gods.

8. I don't know, just looking at the cartoon and the menu it took me approx. 15 seconds to realize that I could do it with giving them all Fresh Fruit, since the order did not specify a mix of appetizers that is exactly what I would do.

9. "Assuming the one sandwich represents the end of the menu" methinks you need to brush up on your reading skills. The \$15.05 of food is explicitly stated to come from the list of APPETIZERS, not APPETIZERS AND ONE SANDWICH.

10. ... Then xkcd shouldn't indent the sandwiches under appetizers!

11. actually paying the bill is the same problem.

12. Any chance of an expanded version explaining all that? I'm feeling thick ATM ;)

13. You could express all the values in cents instead of dollars. That way, all they values would be integers and you wouldn't need to worry about floating-point rounding errors.

14. ...Or use rationals, or use decimals.

15. If you can show me more than one restaurant that includes a list of sandwiches in the appetizer section, I'll eat my hat.

16. Go for the dynamic programming solution.

17. See my next blog entry for a better solution. I use plain recursion and integers, but keep the sandwich. (It makes my solutions stand out from the crowd).

P.S. @Anon: "More than one restaurant...", So you admit we agree on one :-)

P.P.S. @ruiaf and others: Dynamic programming is a nice name, but I don't get its applicability after reading the Wikipedia entry? If you do a DP solution then please link to it here.

18. Paddy, you clearly have very little training with algorithms. Do you know what big-O notation is?

Dynamic programming reduces the solution time from exponential to pseudopolynomial. Why is this important? Neither of your solutions scale well. Many "real-world" applications of the knapsack problem, some of which appear in the world of cryptography. In these cases, you'll have far more than 6 items. You might also run into a case where each item has an associated value, and you want to maximize it while staying under the weight (which, incidentally, is how the original knapsack problem is worded).

Point being, your solution will not be very useful in any other case other than this.

19. @Anon: Your post is irrelevant, Paddy already declared his solution as a bruteforce one. Other than that his programme solved the given problem. You might be very clever, but seriously lack the sense for fun.

20. @Anon, (the one going on about dynamic programming), drone, drone, drone. Show me the code!

I penned a useful (true) knapsack problem elsewhere on my blog that is also on Rosetta Code.

Check out the WP entry for dynamic programming and state where the optimal substructure, and overlapping subproblems lay for example.

As for training and big-O notation and scalability, it is easy to say. Try and apply DP and see how far you get. I doubt you can do better than this, or my second, simpler version in terms of big-O. but I would be enriched if you could, so please try.

21. dynamic programming guyTue Jun 16, 12:06:00 am

http://pastebin.com/m3c71247b

The execution times for the given problem are almost identical. However, if you bump up the target price to say, \$220, the differences are quite notable.

I probably could wheedle some more optimization out of it: the most obvious one is to divide the weights (meal prices) and the target (knapsack capacity) by their GCD to reduce the size of the arrays and I'm sure there are some more non-obvious ones a smarter person could find. I wasn't positive on the best way to force it to get exactly the price in question, so my method of doing that might have been suboptimal.

Note that this is about 25 or so minutes of work, so I may have one or two bugs, but it seems to work well.

I don't do well with commenting on code, but if you have a question, ask and I'll do my best to explain.

22. dynamic programming guyTue Jun 16, 12:15:00 am

PS, it doesn't yield all solutions; just any that work. Finding all solutions would certainly complicate the code.

23. Hi DP Guy,

It returned a list of 7 instances of the string 'FRENCH FRIES' followed by 2426 instances of 'MIXED FRUIT'.

Your original snippet does the same.

I didn't understand your last comment. surely any solution that works would be the same as all solutions?

P.S: Python 2.6.1

24. dynamic programming guyTue Jun 16, 10:29:00 pm

Oh, I forgot to change the target price back to 1505 (change 523515 to that in the last line).

The knapsack problem is interested in any solution (that is, it will find any that maximizes value for items that can fit inside the knapsack). In other words, it returns one solution that works.

25. Half-cent fairy dust. A sprinkle here, a sprinkle there, pretty soon your talkin' real mony.

26. I think you should have set aside at least 15% for tip. Leaving only \$12.79 for food items. Poor waiter.

27. i love the elegance of brute force... :+)

far better than getting bogged down
in unfunny programming discussions.

-bowerbird

28. Hi Bowerbird,

Stay happy :-)

29. In case you care, it's barbecue, not barbeque.

30. To that Anon. who knows how to spell barbecue: thank you. It's appreciated, although I probably won't fix the post due to the clunky Blogger HTML editor that seems to have a, (warped), mind of its own.

31. Appetizers is a heading. Sandwiches is a heading. Sandwiches are not part of Appetizers. A sampler plate is a mixture of the aforementioned appetizers. The indentation argument is irrelevant since it is on an angle and is hand drawn - you might as well argue side salad is indented because the artist drew a lump on the paper at that point.