views:

588

answers:

4

EDIT:

I'm told that making you guys read means I get less attention. My apologies. Here's a simpler version:

Bill got $100 dollars worth of items from a store.

He wants to return enough of the items to get exactly $30 dollars back.

The store has a Point of Return system that will help him do this.

Here is the data after he scans his items:

       item ¦   price ¦

socks             4.00
cheap tv         22.00
book on tape      9.00
book on paper     7.00
party hats        3.00
picture frame    10.00
hammer            5.00
juicer           16.00
mysql guide      24.00

total items  ¦ total price ¦
            9   100.00

Option 1
===============
item ¦          price ¦
cheap tv        22.00
party hats       3.00
hammer           5.00
===============

Option 2
===============
item ¦          price ¦

socks            4.00
picture frame   10.00
juicer          16.00
===============

Option 3
===============
item ¦          price ¦

book on tape    9.00
hammer          5.00
juicer         16.00

I probably missed a few options, since I made all of this up.

So, the big question is:

Is there a way (with GROUP BY, probably) to have one query that would return ever possible combination of items?

Thanks!

a

A: 

i don't think group by can do it.

i can't think of a better way than finding/trying all of the permutations, either in your programming language of choice or with a stored procedure.

if you had items over 30$ you could omit them.

there would be some improvements if you wanted a "best" option by some criteria.

benlumley
Omitting items is a great idea. Unfortunately, in the real scenario I'm dealing with trading time, so somewhere down the line it may be a feature to take part of a larger shift. But that could be handled separately, come to think about it...
Anthony
+2  A: 

You're asking for all subsets which sum up to exactly $30.

This sounds a lot like the subset sum problem, and knapsack problem, so I strongly doubt you can do this with a simple query. You'd probably have to turn to T-SQL, but even that would probably look ugly.

I think programming is the way to go here.

csl
SQL enumerates combinations via a join. You'd need an indefinite number of joins to compute all combinations of all items. This explicitly CANNOT be done in SQL.
S.Lott
But T-SQL is Turing complete... :) But it would probably look ugly.
csl
Mike Woodhouse
+1  A: 

If the number of items are small enough you can brute force this with SQL. This might be a quick to write solution, but you probably want to do something smarter. Sounds like the "knapsack problem" which is NP complete.

If the number of items is large, you will need to delve into dynamic programming algorithms. You have to ask yourself how important this is to your application.

If the number of items is relatively small, you may be able to brute-force this. A brute-force SQL statement (which is what you asked for) that finds combinations of 1,2 or 3 items that match is as follows. If this is not satisfactory, then maybe SQL is not the right tool for this job.

SELECT
   i1.id AS id1,
   NULL AS id2,
   NULL AS id3,
   i1.amount
FROM
   items i1
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount AS total
FROM
   items i1,
   items i2
WHERE
   i1.amount + i2.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount + i3.amount AS total
FROM
   items i1,
   items i2,
   items i3
WHERE
   i1.amount + i2.amount + i3.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id AND
   i2.id <> i3.id

In Oracle, you would use the CUBE function to turn this into a generic version, not sure about a MySQL equivalent.

WW
Big props for pointing me to the name of this situation. I've spent days looking at triangular numbers to see if the situation could be simplified. I'm thinking it's actually not a good idea to offer this feature afterall.
Anthony
A: 

This problem is in fact P/NP. eg You probbably can't find THE BEST fitting article prices, without brute force search, and if your clients store is big - you can find that search very long lasting.

You can use some of the existing algorithms that can give you pretty good guess, but I'm affraid that they are all non-SQL ones.

I would suggest to do approximation of your problem:

Create procedure/querry that finds ONE article that best fitts wanted price, and than call it again for new change you have. Not perfect, but will do the job.

dmajkic