The Math of Optimal Shopping Sprees

April 16, 2006 2:28 PM

I need to spend at least $25 at the grocery store to claim a discount. I want to minimize how much I go over $25. I have a list of a half a dozen items I want and their prices. Is there a program that can generate shopping lists that would meet the criteria? I want more than just the optimal list because I can get this discount repeatedly and I don't want to buy the same thing each time.
posted by storybored to work & money (15 comments total)

I'd have thought that an Excel sheet could produce something for you; but a bit of programming would be required. But, probably better, why not just carry a calculator (or use your cellfone's) while you wander round the store? That way you buy what you want, AND make sure you only just go above $25.
posted by jamescridland at 2:37 PM on April 16, 2006

This is a trivial problem to solve if you're a programmer. But it's so specific that there is probably not an existing program to do exactly this (especially since there has to be some way to enter the products you (may) want into the system.

You might be able to get excel to spit out a list like this, if you knew some VB (or VB.net). If you're not a programmer then you may want to just work up 4 or 5 different grocery lists that meet your criteria and leave it at that. This may be even better than a computer program, because the program won't know things like "almost never buy mustard, since it lasts months" and so a program might spit out hundreds of shopping lists that, while they accomplish the mathematical goals (being over $25 but less than $26) will have lots of sub-optimal lists in them. Just sayin'.
posted by zpousman at 2:48 PM on April 16, 2006

Suggestion: Don't worry about optimal lists. Instead, buy multiple units of easy-to-store, non-perishable items you will always need. Cans of soup, cans of soda, toilet paper, shaving cream, bars of soap, etc.
posted by frogan at 2:49 PM on April 16, 2006

Is the grocery store thing a metaphor for some other type of situation?
A program seems a bit overkill if there are only 6 items with known prices.

If you really wanted to, you can just tabulate.
What combination gives you close to but at least $1, $2, $3 etc? You do this recursively of course: If you have an item that's priced at say $5 then to discover what combinations will give you $25, you can use one of that $5 item plus any of the combinations that work for $20.
posted by juv3nal at 2:54 PM on April 16, 2006

isnt this 1d bin-packing? and as such is NP-hard? IIRC then there is no polynomial-time algorithm that can optimally solve the problem, just approximations. i was really bad at computational theory though...
posted by joeblough at 3:12 PM on April 16, 2006

Isn't this like a packing problem? I would order all the relatively inexpensive products (e.g., under five dollars) that you would consider buying into ascending order of price. Carry that list with you to the supermarket. Go and shop for whatever you want, keeping the total a few bucks under $25. Then select an item or two from your list that will take you over the top. This way you won't be a slave to the list, since most of your items will be chosen according to your needs or appetite.
posted by weapons-grade pandemonium at 3:21 PM on April 16, 2006

isnt this 1d bin-packing? and as such is NP-hard? IIRC then there is no polynomial-time algorithm that can optimally solve the problem, just approximations. i was really bad at computational theory though...

Hmm, I think it may be, however there are only six items and $25 total, so you could still search exhaustively.

The NP-ness, however, would make it impossible to do by hand.
posted by delmoi at 3:23 PM on April 16, 2006

Perhaps I'm missing the point, but isn't this the exact problem that solver was built for?

If I understand the question correctly, I think I could do this in under 2 minutes without touching VBA. All you need to do is change a constraint (say, buy no more than three cans of spinach, then buy no more than two cans, etc)
posted by Kwantsar at 4:01 PM on April 16, 2006

This is exactly the packing problem. Excel can do this; a perl script can do this; you can do this by hand (and you can approximate fairly easily, especially if you know the distribution of prices of your items).
posted by devilsbrigade at 4:07 PM on April 16, 2006

The NP-ness, however, would make it impossible to do by hand.

The general problem is impossible, but with 6 items/$25?
A dynamic programming approach gives you something in O(NxM), and assuming "to within a dollar" is good enough for you, that should yield a table with only 150 elements unless I'm missing something.
posted by juv3nal at 4:22 PM on April 16, 2006

I second the Excel solver.

Is this coupon available to others? On the Internet? How can I get one of these coupons?
posted by Frank Grimes at 7:29 PM on April 16, 2006

yeah, i guess i didnt even read the OP well enough to see that it was a trivial # of goods. i just got went all academic on everyone's ass for no good reason :)
posted by joeblough at 7:30 PM on April 16, 2006

I just do what frogan said -- buy non-perishable items.

Before they pass the least important items through the barcode reader, just ask "how much does this total to?" and leave the extra items you don't need.
posted by Sharcho at 5:52 AM on April 17, 2006

Backing up a bit... If you want to use this program repeatedly, how are you going to keep track of price changes? You can't just set everything up in your Excel spreadsheet and assume that you're ready to go, since prices are changing every week, sometimes faster. I agree that it's more practical to just keep track of the total as you're shopping (with calculator) or else ask at the checkout what is the total and then leave the items you don't want.
posted by Robert Angelo at 7:24 AM on April 17, 2006

Thanks for the answers everyone. I basically took the manual approach and figured out three options on paper using a calculator. I was curious to know if there was a website/utility that did this with minimal learning curve but after checking out the suggestions, the calculator was just plain faster.

But it was so cool to tie this to packing problems and NP completeness! That is very neat.

Frank, the coupon's only available here in Ottawa, Can. at a particular store, today.
posted by storybored at 12:07 PM on April 17, 2006