Compare a Number with sum of subset of numbers

oracle, plsql, sql, subset-sum

Solution

You don't need PL/SQL to solve this. This is an extremely interesting problem to be solved with SQL alone, and I've written up a blog post to explain my answer in more detail.

The way you've presented your question, I'm assuming you're not really solving the subset sum problem, but a simpler problem where you want to compare a number to a very limited set of subsets, namely the ones that are ordered by `WORK_AMT` ascendingly, with no gaps.

Simplified problem

This can be solved with Oracle SQL alone:

WITH
    ASSIGN(ID, ASSIGN_AMT) AS (
                  SELECT 1, 25150 FROM DUAL 
        UNION ALL SELECT 2, 19800 FROM DUAL
        UNION ALL SELECT 3, 27511 FROM DUAL
    ),
    VALS (ID, WORK_AMT) AS (
                  SELECT 1 , 7120  FROM DUAL 
        UNION ALL SELECT 2 , 8150  FROM DUAL
        UNION ALL SELECT 3 , 8255  FROM DUAL
        UNION ALL SELECT 4 , 9051  FROM DUAL
        UNION ALL SELECT 5 , 1220  FROM DUAL
        UNION ALL SELECT 6 , 12515 FROM DUAL
        UNION ALL SELECT 7 , 13555 FROM DUAL
        UNION ALL SELECT 8 , 5221  FROM DUAL
        UNION ALL SELECT 9 , 812   FROM DUAL
        UNION ALL SELECT 10, 6562  FROM DUAL
    ),
    SUMS (ID, WORK_AMT, SUBSET_SUM) AS (
        SELECT VALS.*, SUM (WORK_AMT) OVER (ORDER BY ID)
        FROM VALS
    )
SELECT
    ASSIGN.ID, 
    ASSIGN.ASSIGN_AMT, 
    MIN (SUBSET_SUM) KEEP (
        DENSE_RANK FIRST
        ORDER BY ABS (ASSIGN_AMT - SUBSET_SUM)
    ) AS CLOSEST_SUM
FROM
    ASSIGN
CROSS JOIN
    SUMS
GROUP BY
    ASSIGN.ID, ASSIGN.ASSIGN_AMT

The above yields:

ID  ASSIGN_AMT  CLOSEST_SUM
---------------------------
1   25150       29085
2   19800       20935
3   27511       29085

The actual subset sum problem

Beware that this problem has exponential complexity in time and space. It can only be solved reasonably for a small amount of values in the `WORK` table!

WITH
    ASSIGN (ID, ASSIGN_AMT) AS (
                  SELECT 1, 25150 FROM DUAL 
        UNION ALL SELECT 2, 19800 FROM DUAL
        UNION ALL SELECT 3, 27511 FROM DUAL
    ),
    WORK (ID, WORK_AMT) AS (
                  SELECT 1 , 7120  FROM DUAL 
        UNION ALL SELECT 2 , 8150  FROM DUAL
        UNION ALL SELECT 3 , 8255  FROM DUAL
        UNION ALL SELECT 4 , 9051  FROM DUAL
        UNION ALL SELECT 5 , 1220  FROM DUAL
        UNION ALL SELECT 6 , 12515 FROM DUAL
        UNION ALL SELECT 7 , 13555 FROM DUAL
        UNION ALL SELECT 8 , 5221  FROM DUAL
        UNION ALL SELECT 9 , 812   FROM DUAL
        UNION ALL SELECT 10, 6562  FROM DUAL
    ),
    SUMS (SUBSET_SUM, MAX_ID) AS (
        SELECT WORK_AMT, ID FROM WORK
        UNION ALL
        SELECT WORK_AMT + SUBSET_SUM, GREATEST (MAX_ID, WORK.ID)
        FROM SUMS JOIN WORK
        ON SUMS.MAX_ID < WORK.ID
    )
SELECT
    ASSIGN.ID, 
    ASSIGN.ASSIGN_AMT, 
    MIN (SUBSET_SUM) KEEP (
        DENSE_RANK FIRST
        ORDER BY ABS (ASSIGN_AMT - SUBSET_SUM)
    ) AS CLOSEST_SUM
FROM SUMS 
CROSS JOIN ASSIGN
GROUP BY ASSIGN.ID, ASSIGN.ASSIGN_AMT

This now yields:

ID  ASSIGN_AMT  CLOSEST_SUM
---------------------------
1   25150       25133
2   19800       19768
3   27511       27488

Problem

I am looking a guidance of your gurus to find out a way to Compare a Number with a sum of subset of numbers like ``` DECLARE L_NUM_TO_COMPARE NUMBER := 0; L_NUM_SUBSET NUMBER := 0; BEGIN FOR MAIN_REC IN ( SELECT 1 ID, 25150 ASSIGN_AMT FROM DUAL UNION ALL SELECT 2 ID, 19800 ASSIGN_AMT FROM DUAL UNION ALL SELECT 3 ID, 27511 ASSIGN_AMT FROM DUAL ) LOOP L_NUM_TO_COMPARE := MAIN_REC.ASSIGN_AMT; DBMS_OUTPUT.PUT_LINE( L_NUM_TO_COMPARE); FOR C IN ( SELECT 1 ID, 7120 WORK_AMT FROM DUAL UNION ALL SELECT 2 ID, 8150 WORK_AMT FROM DUAL UNION ALL SELECT 3 ID, 8255 WORK_AMT FROM DUAL UNION ALL SELECT 4 ID, 9051 WORK_AMT FROM DUAL UNION ALL SELECT 5 ID, 1220 WORK_AMT FROM DUAL UNION ALL SELECT 6 ID, 12515 WORK_AMT FROM DUAL UNION ALL SELECT 7 ID, 13555 WORK_AMT FROM DUAL UNION ALL SELECT 8 ID, 5221 WORK_AMT FROM DUAL UNION ALL SELECT 9 ID, 812 WORK_AMT FROM DUAL UNION ALL SELECT 10 ID, 6562 WORK_AMT FROM DUAL ORDER BY 2 DESC ) LOOP L_NUM_SUBSET := NVL(L_NUM_SUBSET,0) + C.WORK_AMT; DBMS_OUTPUT.PUT_LINE( L_NUM_SUBSET); /* I NEED TO PUT SOME LOGIC HOW CAN I FIND NEAREST SUM OF SUBSET */ IF MAIN_REC.ASSIGN_AMT = L_NUM_SUBSET THEN DBMS_OUTPUT.PUT_LINE( L_NUM_SUBSET); END IF; END LOOP; END LOOP; END; ``` I have been searched this forum and found a question Sum of Sub set of numbers which is nearly a same requirement of me, what I need can some one point me how can I do this in PL/SQL I have (Oracle DB 11g R2)

Original source