Mainly Tech projects on Python and Electronic Design Automation.

Monday, June 15, 2009

XKCD Simpler Knapsack Solution

 After reading the feedback on my href=""
target="_blank">earlier solution to the XKCD knapsack problem,
I decided to re-write it without itertools.product and with integer

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

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


  1. Short recursive mathematica program:

  2. I got a minor nit to pick (in your data not your answer)
    barbecue does not belong in the list
    go back and read the comic it is 15.05 of appetizers the barbecue is a sandwich not an appetizer.
    sorry i am done being picking nits now

  3. Yet you still are including "barebecue" in the list. I don't know if you are slightly retarded or what, but no restaurant ever includes a list of sandwiches in the "appetizer" section. The fact that the list of sandwiches was CUT OFF should make you realize that it's not supposed to be included.

  4. @Anonymous: I think that you are being extremely rude in your comment. If he likes to include a sandwich, why should you feel entitled to insult him, furthermore in such a harsh way? Go ahead, remove the Barbeque from the tuple and you will find your desidered solution and the world will be a better place. By the way, learn to spell.

  5. (Are Anon. posts always the most rude)?

    @Anon: I would suggest that my keeping of barbecue is much less of a retardation than your use of tone in a comment.

  6. Hi David,

    I took a look at your Mathematica solution, and although I don't know the language, I could not see where the exactcost of 15.05 is given? (I did like the formatting of the table though).

    - Paddy.

  7. As an FYI, a nice way of solving such a problem is using constraint programming (CP). There is a solution to this instance written using a Ruby-interface to a CP library here (that it is in Ruby is in no way essential):

  8. Thanks Anon, I did look at the CP solution.

  9. I realise that the community who reads this blog are generally programmers, but as one myself, could the anonymous programmers please help the entire world realise that we aren't all pedantic retarded fuckwits by taking all the fun out of what Paddy is trying to do?

  10. Unfortunately, they never specified if that $15.05 was to be before or after tax...

  11. Hi again Anon. Ruby CP solution guy (who turns out to be Hakan). Does your CP solution give all results? from the little I know, it probably will.

    I know some CP methodologies give you an easier way to state a problem, but was wondering, for this case, if you had to find *all* solutions, if CP does something extra that reduces the time complexity w.r.t. what I did? (Genuine question, I'm not trying to diss you).

    - Paddy.

  12. Hi,

    I'm not Hakan, I just knew he had a nice solution up.

    You can get all solutions by asking the system for them, given that you know the minimum number of items required. Thus two searches are needed, one to find the minimum (as is done in the example) and one to find all solutions with that minimum. Hakan has an example on his page solving the cryptarithmetic problem SEND?MOST=MONEY for all maximal values of money:



Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

Blog Archive