Eating NP-completely at Mcdonalds

Ever since I was a child I have always been aware of and appreciated the difficulty involved in solving NP-complete problems. While the other children were out at their tables eating their food, I would stand often, trying to decide just what choices would allow me to get the most value for my money. It was a treat you see, so we didnt get to do it all the time. I used to take a long time making decisions, over analyzing decision paths whose relevance might be deemed questionable. I still do this actually, much to the amusement (and often frustrated bemusement of my friends). As an example, one of my favourite eat out treats was going to McDonalds. I realized that rather than buying unfilling happy meals I could do better by buying a number of individual sandwiches and fries separately for a similar price.

I still like to go to mcdonalds and still take time (counted in minutes) trying to optimize my cost-value ratio. Having recently gotten an Acer n310, the solution was simple. Use the knapsack algorithim to decide how to pack as much McDonalds for the price I wish to pay into my stomach while also cutting time and ensuring that I am actually making a good choice. So I did that.

The program was written on .NET 2.0, in F# and it runs on both my PocketPC and on my PC. I built the F# dll and then slapped a GUI on it using Visual C# for both versions.

At the moment the menu is hard-coded in and so are the costs and value function. The program works well enough. It validated some of my choices (3 hamburgers and 1 fillet, 1 small fries was fair for a £5 limit) while showing that with other choices by varying a single item I could have gotten more value for a bit less. The code is not very long, the knapsack contents function and .net interfaces are given below:

let rec bag_contents cost_i (best_items_per_cost : int array) =     

    match cost_i with
        | _ when cost_i <= 0 -> []
        | cost_current -> cost.[0] <- cost_current
                          let next_item = cost_current - cost.[best_items_per_cost.[cost_current]]               
                          best_items_per_cost.[cost_current]::(bag_contents next_item  best_items_per_cost)

//....
//Exposed using:
let rec mkString xs = 
    match xs with
        | [] -> ""
        | x :: xs ->  if x > 0 then assoc_list.[x-1] + " | " + (mkString xs) else " | " + (mkString xs)

type Knap = class
     new () = {}
     member this.Packed_Bag cost_size_preffered = mkString (best_bag cost_size_preffered size_menu)
end

Some things I wish to do is allow feeding of textfiles of items and cost/value functions (merely tables). As well I would like to do suggestions and variety. At the moment for example it tells me that Fries,Fries,Fries,Fries is good for £3.56. This is to be expected given the nature of the algorithm. But something like, for Np (where N is an integer) more or less you might try this combination or getting this or that item. So it’d also take a range |k| when making suggestions.

Defining value is tricky as well but that cant be helped.

Numeric updown in .NET compact doesnt support decimals.