SQL - select subset of IDs where sum(A) <= X and sum(B) is biggest

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.

Answer 1

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.

Answer 2

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