Print Story Programming Fun Challenge: Food on Expenses
Software
By codemonkey uk (Thu Jun 18, 2009 at 01:18:21 PM EST) (all tags)
So, it' is that time of the project again, and I am working late.  When we work late, we get food on expenses.  The problem is, there is an limit on how much each person can claim on expenses.  Now, for the pizza ordering guys this isn't a problem, but the chaps ordering a curry might want a main dish, some rice, and a naan bread of poppidom, which might be just over the limit.

Wait, you say.  This was supposed to be a PFC.  Don't feel tricked!  Read more inside.



Problem:  Packing items of fixed size into containers of fixed size, to maximize the total number of items contains, according to a basic priority system, so that all mains are ordered and as many sundries are also ordered.

Ie, given:


max_cost=9

thad=pizza £7
bob=curry £8, rice £2

The program would produce:

max_cost=9

thad=pizza £7, rice £2
bob=curry £8

Bonus points if you make it a webservice of some sort.  :D

< Let the soul-sucking commence! | The Complication of relationships >
Programming Fun Challenge: Food on Expenses | 14 comments (14 topical, 0 hidden) | Trackback
back in the stone age by clover kicker (2.00 / 0) #1 Thu Jun 18, 2009 at 01:31:17 PM EST
I remember reading about some guy's intern job at MS, he wrote a very similar script to organize installation files onto floppy diskettes.

ISTR he shaved 1 floppy diskette from the Windows 3.0 installation set, the company must have saved 10s of millions.


Please insert disk 9 of 13 and press any key to continue.

P != NP ? by sasquatchan (2.00 / 0) #2 Thu Jun 18, 2009 at 01:34:21 PM EST
Can't tell if you're trolling me or not... Granted, IIRC the best fit or first fit are the typical heuristics for the bin packing problem..

Now by flowergrrl (4.00 / 2) #3 Thu Jun 18, 2009 at 01:38:56 PM EST
 I want a curry  :(

On working late... by belldandi (2.00 / 0) #4 Thu Jun 18, 2009 at 01:40:02 PM EST
I think I remember from prior posts that you work for a gaming company no? I just had another friend who's going into a hidey-hole until Thanksgiving so he can get Assassin's Creed out.

First, we assume a perfectly sperical curry... by wiredog (4.00 / 3) #5 Thu Jun 18, 2009 at 02:03:41 PM EST


Earth First!
(We can strip mine the rest later.)

Ummm, spHerical. by wiredog (2.00 / 0) #6 Thu Jun 18, 2009 at 02:04:11 PM EST
Preview is my friend.

Earth First!
(We can strip mine the rest later.)

[ Parent ]
An MP writes by anonimouse (4.00 / 4) #7 Thu Jun 18, 2009 at 02:12:30 PM EST
The solution to the problem is simple; find a delivery company that will write receipts for any amount you like and put the entire bill on that, plus hookers. There are many minor variations on this well recognised method to solve the packing problem


Girls come and go but a mortgage is for 25 years -- JtL
Clarification sought by Herring (2.00 / 0) #8 Thu Jun 18, 2009 at 02:26:22 PM EST
If the allowance is £9 per person, can two people share an £18 pizza (I don't know what sort of pizza would cost this much, but it would have to be awesome)?

christ, we're all old now - StackyMcRacky
It would also by hulver (4.00 / 2) #9 Thu Jun 18, 2009 at 02:44:12 PM EST
Have a donner kebab on top.
--
Cheese is not a hat. - clock
[ Parent ]
This reminds me by Herring (4.00 / 2) #12 Thu Jun 18, 2009 at 03:09:46 PM EST
When are we going to have the 7 rating feature enabled?

Enhancement description
Actors: Trusted users/cabal members
Main flow: When the actor spots an exceptional comment, they should have a button or other control available that gives the comment a rating of 7.

Only two 7 ratings can be given in any calendar month.

Post conditions: The user's Ghetto 7 allowance for the month is

ah fuckit

christ, we're all old now - StackyMcRacky

[ Parent ]
+7 by hulver (4.00 / 1) #13 Thu Jun 18, 2009 at 03:25:51 PM EST

--
Cheese is not a hat. - clock
[ Parent ]
Isn't this just the knapsack problem? by fluffy (4.00 / 2) #10 Thu Jun 18, 2009 at 02:52:43 PM EST
Except with multiple sacks?

busy bees buzz | sockpuppet revolution
I think it's closer to bin packing by sasquatchan (2.00 / 0) #11 Thu Jun 18, 2009 at 03:07:21 PM EST
but for extra credit, reduce it to TSP or SAT.

[ Parent ]
PFC entry by holereader (4.00 / 2) #14 Tue Jun 23, 2009 at 05:57:15 PM EST
I'm not sure if you were joking, but this made a decent excuse to work on my JavaScript/DOM skills.

http://pastebin.ca/1471744

Programming Fun Challenge: Food on Expenses | 14 comments (14 topical, 0 hidden) | Trackback