MySQL finding subtotals

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

This problem is in fact P/NP. eg you probably 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 afraid that they are all non-SQL ones.

I would suggest to do approximation of your problem:

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