Journal

Sign in to follow this  
  • entries
    122
  • comments
    246
  • views
    89731

Eating NP-completely at Mcdonalds

Sign in to follow this  
Daerax

355 views

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.
Sign in to follow this  


3 Comments


Recommended Comments

Haha I know where you're getting at, because 3 nights ago me and my friends got totally ripped off at a local bar. We each paid 3€ for 2 beers when each one cost 1.20€ and the drinking minimum was 2€. How? Taking advantage of a supposed "promotion" for 5 beers at a cheaper price, putting it on my tab and splitting the cost! Damn, did I ever felt stupid :) BTW at some places you can get a good beer for 0.50€ or 0.40€ (yeah, that cheap).

Share this comment


Link to comment
You may just have too much time on your hands. [grin]

This would actually be really cool to use at almost any dining establishment, though especially at McDonalds since the food there is dirt cheap.

I think you should also write a paper: On Solving Small Instances of the Knapsack Problem to Determine Optimum Purchasing at Fast Food Establishments on a Portable Device

Share this comment


Link to comment
Quote:
Original post by Ravuya
You may just have too much time on your hands. [grin]

This would actually be really cool to use at almost any dining establishment, though especially at McDonalds since the food there is dirt cheap.

I think you should also write a paper: On Solving Small Instances of the Knapsack Problem to Determine Optimum Purchasing at Fast Food Establishments on a Portable Device


Hey this is ground-breaking stuff here! Think how many parents would be dying to get their hands on this. hehe. I actually plan on using it though when im at mcdonalds. Just doing some fine tuning.

As for the paper, I should get around to that, no doubt it will lead to my winning the nobel peace price.

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