XKCD Simpler Knapsack Solution

 After reading the feedback on my href="http://paddy3118.blogspot.com/2009/06/xkcd-knapsack-solution.html"
target="_blank">earlier solution to the XKCD knapsack problem,
I decided to re-write it without itertools.product and with integer
maths.



I came up with a solution that used explicit while loops that worked,
and used much less traversals through nested loops, but I then boiled
that down to a recursive solution which retains the ability to easily
modify the number of dishes , whilst restricting the number of times
through the loops to the bare minimum.



In the previous solution I worked out the maximum number of each dish
that cost less than or equal to the amount and looped from zero to that
many times. In the solution below the while loops cut off looping on
any particular dish when adding another would put the cost over the
maximum.



And now the code:

items = ( ('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)
 color="#0000ff"># All calcs in integer cents.
prices = [int(price*100)  color="#804040">for price  color="#804040">in prices]
ecost = int(exactcost*100)

 color="#0000ff"># counts of each dish
dishcounts = [0]*len(prices)
 color="#0000ff">possibleorders = []
cost = 0
maxnesting = len(dishcounts)

 color="#804040">def  color="#008080">enumeratedish(nest, cost, possibleorders):
     color="#804040">global dishcounts, prices, ecost, maxnesting
     color="#804040">while cost <= ecost:
         color="#804040">if nest+1 < maxnesting:
            enumeratedish(nest+1, cost, possibleorders)
         color="#804040">elif cost == ecost:
            possibleorders.append(dishcounts[:])
             color="#804040">break
        dishcounts[nest] += 1
        cost += prices[nest]
         color="#0000ff">#print (dishcounts)
    cost -= prices[nest] * dishcounts[nest]
    dishcounts[nest] = 0

enumeratedish(0, 0, possibleorders)
 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:
    order = zip(dishes, order)
     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]))

feel free to compare the two solutions.