MySQL finding subtotals
EDIT:
They tell me that making you guys read means I pay less attention. My apologies. Here's a simpler version:
Bill got $ 100 apiece at the store.
He wants to return enough items to get exactly $ 30 back.
The store has a return system to help him do this.
Here's the data after scanning 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 did it all.
So the big question is:
Is there a way (with GROUP BY, perhaps) to have a single query that will return all possible combinations of elements?
Thank!
and
source to share
If the cardinality is low enough, you can overdo it with SQL. It can be quick to write a solution, but you probably want to do something smarter. It looks like the problem with the backpack "which is NP complete.
If the number of items is large, you will need to delve deeper into dynamic programming algorithms. You have to ask yourself how important this is to your application.
If the item count is relatively low, you can redirect this. A brute-force SQL statement (which you asked for) that finds combinations of 1,2 or 3 items that match as follows. If this is unsatisfactory, then SQL may not be suitable for the 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 have to use the CUBE function to turn it into a generic version, not sure about the MySQL equivalent.
source to share
You are asking for all subsets that add up to exactly $ 30.
This is very similar to the subset summation problem and the knapsack problem , so I highly doubt you can do it with a simple query. You may have to turn to T-SQL, but even that will probably look ugly.
I think programming is the way to go here.
source to share
I don't think the band can do that.
I can't think of a better way than to find / try all permutations, either in your programming language of choice or in a stored procedure.
If you have items over $ 30, you can omit them.
there would be some improvements if you wanted to choose the "best" according to some criteria.
source to share
This problem is actually P / NP. for example, you probably cannot find the BEST prices for suitable items without brute force searching, and if your customer store is large, you may find this search very durable.
You can use some of the existing algorithms which might give you pretty good guesses, but I'm afraid they are all non-SQL.
I would suggest approaching your problem:
Create a procedure / query that finds one article that best matches the desired price and calls it again for new changes. Not perfect, but will do the job.
source to share