1

I'm looking now at the subset sum problem... inspired from this post.

It's an interesting problem.. Here we create two tables

  1. foo with 1,000 rows (id,rand) between 5..105
  2. bar with 10 rows (id,rand) between 1..1,000

Source code to generate them is as follows.

CREATE TEMP TABLE foo
AS
  SELECT x AS id,
    trunc(random()*100)+5 AS rand
  FROM generate_series(1,1000)
    AS t(x);

CREATE TEMP TABLE bar
AS
  SELECT x AS id,
    trunc(random()*1000) AS rand
  FROM generate_series(1,10)
    AS t(x);

Now the goal is to find whatever combinations of foo sum closest to the row in bar without going over.

Ideally, I'd like something like this.

bar.id  bar.rand   foo.ids              foo.sum
1       872        {14,398,72,...etc}   868
  • m! / (n! · (m-n)!) should it calculate the sum of all possible combinations of foo.id ? – McNets Feb 14 '17 at 22:43
  • 4
    I am not sure at all that this is the kind of problem that can be solved in a close-to-optimal manner by using SQL. This is normally the kind of problem that can be solved using some kind of tree approach, and pruning (or not exploring) branches you already know will not comply, or whose result will be worse than the best that you've already checked through the leafs. You can do trees with recursive-CTEs... But I don't have any idea about how to something equivalent to pruning them. – joanolo Feb 15 '17 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.