• entries
122
246
• views
89777

# Eating NP-Completely in McDonalds Again

564 views

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

with

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  = 0maxval 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.

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

Steve

hehe. got kinda annoying really quick.

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.

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

## Create an account

Register a new account