比较一个数字与一组数字的子集之和

Question

我希望您的专家能提供帮助，找到一种比较数字与一组数字子集之和的方法，例如：

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;

我在论坛上搜索并找到了一个问题，与我的需求几乎相同。链接如下： Sum of Sub set of numbers

请问有没有人可以指导我如何在 PL/SQL 中实现这个功能？我使用的是 Oracle DB 11g R2。

- alhashmiya

---

这是算法中一个相当常见的问题，称为“子集和问题”。通过快速搜索谷歌，您可以了解使用动态规划的算法工作原理。尝试在PL/SQL中实现它，并向我们展示您的工作，如果它不能按预期运行。 - ruudvan

Answer 1

您不需要使用PL/SQL来解决这个问题。这是一个非常有趣的问题，可以仅使用SQL来解决，而我已经写了一篇博客文章，更详细地解释了我的答案。

根据您提出问题的方式，我假设您并没有真正解决子集和问题，而是解决了一个更简单的问题，即要将一个数字与一组非常有限的子集进行比较，这些子集按WORK_AMT升序排序，没有间隙。

简化问题

这可以仅使用Oracle SQL来解决：

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

以上会产生以下结果：

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

实际的子集和问题

请注意，该问题在时间和空间上具有指数复杂度。仅适用于WORK表中少量值的合理解决方法！

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

现在这将产生：

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

- Lukas Eder

---

Likas Eder先生，我希望我能给您的回答点赞100次 :) 您的回答完全解决了我的问题。 - alhashmiya