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
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.