Jump to content
  • Advertisement


Sign in to follow this  
  • entries
  • comments
  • views

Eating NP-Completely in McDonalds Again

Sign in to follow this  


Some time ago I wrote about using the knapsack algorithm to make my spendings in McDonald's as efficient as possible. Ive actually used this program fairly often and it has proven surprisingly useful. However the program always left a certain taste of dissatisfaction in me. Namely, due to how i encoded my value function certain inputs of money e.g. GBP3.56 gave silly outputs like: Fries,Fries,Fries,Fries. So I returned to the program this weekend. But first some background.

What is the Knapsack Algorithm?

The knapsack problem is a problem in optimization. It is often presented as a problem faced by a thief with a certain sized bag. A thief with a bag of size S breaks into a house. There are items of different sizes and values, what items must the thief take to maximize the value of the items in his bag? Or mathematically: Maximize


Where for the t types of items, vi is the value of each type of item, si is size and xi is the number of each kind of item.

One way to solve this is to use something called dynamic programming where we calculate the highest values for every size bag and taking into account every item type. For each item we check how it fits in every size bag up to the size S of our bag. Then for every new item considered we check if the value of what was there previous is less than the value of the new item and what is left when we remove items to make space for the new one in the bag. If less we discard old item and replace with new. Recursively in Haskell:
sub  = (!!)

s = [3 , 2, 1,5]
v = [6 , 3 ,7,10]

maxval 0 = 0
maxval size = maximum [ v `sub` i + maxval (size - s `sub` i ) | i<-[0..t], s `sub` i <= size] where
t = (length s) - 1
The problem is that this recursive solution is poor performance wise and is not very good for large values. However this can be rewritten to use a table - utilizing memoization to improve performance - where previous values are stored and used to calculate new ones.
For every item and every size bag we check (F#):

if (opt_cost.[cost_n] < opt_cost.[cost_n-cost.[item_n]] + value_c ) then
opt_cost.[cost_n] <- (opt_cost.[cost_n-cost.[item_n]] + value_c)
best_n.[cost_n] <- item_n
Values across Ranges

To address the old problem of stupid suggestions I tried introducing bounds and making certain items appear only within certain cost ranges but these were not satisfactory. Finally I decided upon a simple solution. Originally one could say that the value v, for each item was a mapping from my internal preferences to the natural numbers. However this was unsatisfactory so I introduced a range given in the form of a tuple to my value function. Thus instead of each item having a value V, it was a number that could take any value between V and W with V <= W. e.g.:
let value = [|(0,0) ; (20, 23) ; (21,22); (21, 23); (65, 70); (60,65)|]
Then within the bag packing function a random number that falls within each respective range is given to value. This minor addition has proven to be the difference between making my little app fairly useful to very useful. A button on the interface 'New Combo', generates a new combination of items within the price constraint if I am not satisfied with the current combination. Now I know that for GBP3.56 instead of 4 fries I can get 2 hamburgers, french fries and a coke.

The thing runs on my pocket pc and was written in F#. And yes the value function concept is very subjective.

Sign in to follow this  


Recommended Comments

Heh... "fries, fries, fries, fries", that line just made my weekend that little bit more enjoyable, very funny :)


Share this comment

Link to comment
What the hell is a "hambuger"?

Also what currency does the program take? If that's all you can buy for £5.2 then you guys are getting ripped off.

Share this comment

Link to comment
Lol thanks. Mcdonalds hamburgers are not quite hamburgers hence we leave off the r. Anyways ye ill correct the typo. I built it using GBP values.

And yes things are a bit expensive here in UK but compared to average local wages price are not too bad. See Big Mac Index. Fish Fillet, big mac, medium fries and medium coke for 5.20 is not so bad. hehe

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!