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 product

items = ( (' 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.05

dishes, 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]))

The answers I get are:

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).