The Math of Optimal Shopping Sprees
April 16, 2006 2:28 PM Subscribe
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
posted by Robert Angelo at 7:24 AM on April 17, 2006
Response by poster: 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
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
This thread is closed to new comments.
posted by jamescridland at 2:37 PM on April 16, 2006