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, 1 fillets, 1 medium fries was fair for a ~ GBP5 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 GBP3.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.