You should use the Knapsack algorithm. It's difficult to solve it in sql, so I advice you to get all needed data on client and calc then.
SQL - select subset of IDs where sum(A) <= X and sum(B) is biggest
-
30-09-2022 - |
Question
I have table1:
CREATE TABLE table1 (
itemID INTEGER PRIMARY KEY,
cost INTEGER NOT NULL,
income INTEGER NOT NULL
);
I have MYMONEY
amount of money.
I want SQL to give me the best combination of items which I can buy and sell later to get the biggest income (I sell the items after I leave the shop)
In other words:
Get the subset from table1
where sum of cost
in this subset is less or equal to MYMONEY
and the sum of income
is highest.
For instance, if we have a table with tuples (1, 5, 10)
, (2, 3, 6)
, (3, 2, 5)
and MYMONEY=5
subsets where the first condition is met are {(1, 5, 10)}
and {(2, 3, 6), (3, 2, 5)}
. The second condition says that the second subset is better, since sum of income
in this subset is 11, where in the first subset sum of income
is 10.
The point is, that those subsets may have various power. If I had a limit of subset's power, I could easily do it by joining or cross-producting the table enough times and choosing the best row.
I could use a counter c
which says "now let's see only those subsets which power is equal to c
" and use the solution with cross-product, but I find it slow and ugly.
In case there are many "best" subsets it may just give any of them or all, it is of no importance.
If it matters, I am using PostgreSQL and Java.
La solution
Autres conseils
This can be done using SQL:
with recursive calc as (
select itemid as itemid, array[itemid] as id_list, cost, income
from table1
where cost <= 5
union all
select c.itemid, p.id_list||c.itemid, c.cost + p.cost, c.income + p.income
from table1 as c
join calc as p on p.itemid < c.itemid
where c.cost + p.cost <= 5
)
select *
from calc
order by income desc;
But just becaus it can be done, doesn't necessarily mean it's a good idea to do it.
This query will have a horrible performance with any real-world table.
Here is a SQLFiddle: http://sqlfiddle.com/#!15/10455/1