SQL puzzle III.

The third one. Knapsack problem. I see two approaches to solve this task in SQL. They are not very efficient but working ones.

SQL> CREATE TABLE knapsack (
  2    item_number                      NUMBER PRIMARY KEY
  3  , volume                           NUMBER NOT NULL
  4  , value                            NUMBER NOT NULL
  5  );

Table created.

SQL> INSERT INTO knapsack VALUES(1, 77, 2);
SQL> INSERT INTO knapsack VALUES(2, 99, 1);
SQL> INSERT INTO knapsack VALUES(3, 19, 3);
SQL> INSERT INTO knapsack VALUES(4, 91, 1);
SQL> INSERT INTO knapsack VALUES(5,  6, 3);
SQL> INSERT INTO knapsack VALUES(6,  6, 1);
SQL> INSERT INTO knapsack VALUES(7,  3, 1);
SQL> INSERT INTO knapsack VALUES(8, 92, 6);
SQL> COMMIT;

Commit complete.

SQL> VARIABLE capacity NUMBER;
SQL> EXEC :capacity := 92;

PL/SQL procedure successfully completed.

SQL> COLUMN probe NOPRINT
SQL> BREAK ON probe SKIP 1
SQL> WITH bits AS
  2  (
  3    SELECT ROWNUM - 1 bit
  4         , POWER(2, ROWNUM - 1) mask
  5         , volume
  6         , value
  7      FROM knapsack
  8     WHERE volume <= :capacity
  9  )
 10  , pivot AS
 11  (
 12    SELECT ROWNUM - 1 probe
 13      FROM dual
 14   CONNECT BY dummy = dummy
 15       AND ROWNUM <= (
 16             SELECT POWER(2, MAX(bit) + 1)
 17               FROM bits
 18           )
 19  ), combinations AS
 20  (
 21  SELECT probe
 22       , volume
 23       , value
 24       , SUM(volume) OVER (PARTITION BY probe) computed_capacity
 25       , SUM(value) OVER (PARTITION BY probe) computed_value
 26    FROM bits
 27       , pivot
 28   WHERE BITAND(probe, mask) <> 0
 29  )
 30  SELECT probe
 31       , volume
 32       , value
 33       , computed_capacity
 34       , computed_value
 35    FROM combinations
 36   WHERE computed_capacity <= :capacity
 37   ORDER BY
 38         computed_value DESC
 39       , probe
 40       , computed_capacity DESC
 41       , volume
 42       , value
 43  /

   VOLUME     VALUE COMPUTED_CAPACITY COMPUTED_VALUE
--------- --------- ----------------- --------------
        3         1                34              8
        6         1                34              8
        6         3                34              8
       19         3                34              8

        6         1                31              7
        6         3                31              7
       19         3                31              7

        3         1                28              7
        6         3                28              7
       19         3                28              7

        3         1                92              7
        6         1                92              7
        6         3                92              7
       77         2                92              7

        6         3                25              6
       19         3                25              6
...

54 rows selected.

SQL> WITH ordered_items AS
  2  (
  3     SELECT item_number
  4          , volume
  5          , value
  6       FROM knapsack
  7     WHERE volume <= :capacity
  8  ), combinations AS
  9  (
 10  SELECT probe
 11       , volume
 12       , value
 13       , mask
 14       , SUM(volume) OVER (PARTITION BY probe) computed_capacity
 15       , SUM(value) OVER (PARTITION BY probe) computed_value
 16    FROM (
 17         SELECT ROWNUM probe
 18              , SYS_CONNECT_BY_PATH(item_number, ':') || ':' mask
 19           FROM ordered_items
 20        CONNECT BY
 21                item_number > PRIOR item_number
 22         ) c -- all combinations
 23       , ordered_items i
 24   WHERE c.mask LIKE '%:' || i.item_number || ':%'
 25  )
 26  SELECT probe
 27       , volume
 28       , value
 29       , computed_capacity
 30       , computed_value
 31    FROM combinations
 32   WHERE computed_capacity <= :capacity
 33   ORDER BY
 34         computed_value DESC
 35       , probe
 36       , computed_capacity DESC
 37       , volume
 38       , value
 39  /

   VOLUME     VALUE COMPUTED_CAPACITY COMPUTED_VALUE
--------- --------- ----------------- --------------
        3         1                34              8
        6         1                34              8
        6         3                34              8
       19         3                34              8

        3         1                92              7
        6         1                92              7
        6         3                92              7
       77         2                92              7

        6         1                31              7
        6         3                31              7
       19         3                31              7

        3         1                28              7
        6         3                28              7
       19         3                28              7

        6         1                89              6
        6         3                89              6
       77         2                89              6

        3         1                86              6
        6         3                86              6
       77         2                86              6

        6         3                25              6
       19         3                25              6

...