Eating NP-Completely in McDonalds Again

29 03 2008

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. £3.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

\displaystyle \sum_{i = 0}^{t}{v_ix_i}


\displaystyle \sum_{i = 0}^{t}s_ix_i \le S

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 [/source] 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#): [source lang="python"]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[/source] 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 £3.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.