主页 / dba / 问题 / 201674
Accepted
Randomize
Asked: 2018-03-20 06:17:54 +0800 CST

使用 Postgres 根据最接近特定值的总和对数字进行分组

  • 772

我有一张这样的桌子：

 v |   c   
---+-------
 Z |   217
 J |   620
 U |  1891
 F |  3751
 A |  5673
 Y |  5859
 O |  7347
 K |  9827
 I | 11842
 R | 11997
 H | 14818
 M | 18321
 G | 18445
 E | 19220
 D | 22444
 W | 22692
 T | 24428
 P | 26257
 N | 35247
 L | 41416
 C | 42594
 B | 43586
 S | 59613

我如何以一种方式对这些值进行分组，使每个组都具有最接近 60000 的可能值？

例如（可能不是最合适的）：

Z + J + U + F + A + Y + O + K + I + R -- 59024
S -- 59613
B + H -- 58404
etc.
postgresql

1 个回答

  1. Best Answer

    一些研究表明，这个问题在计算机科学中被称为子集和问题。

    在 stackoverflow 上，Lukas Eder 提供了一个类似问题的Oracle 解决方案，并在 jooq 的博客上进行了更长的分析。

    这是源自他的作品的 postgres 版本：

    CREATE TABLE tab(v text, c int);

-- populate table
INSERT INTO tab(v,c) VALUES('Z', 217);
etc...

-- show 10 better results

WITH RECURSIVE sums (subset_sum, max_v, a) AS (
        SELECT
            c,v,array[v] as a
        FROM
            tab

        UNION ALL

        SELECT
            c + subset_sum,
            v,
            array_append(a, v)
        FROM
            sums
        JOIN
            tab
        ON sums.max_v < tab.v
    )
SELECT subset_sum, a FROM sums WHERE subset_sum <= 60000
ORDER BY 60000-subset_sum
LIMIT 10;

    示例数据的结果是：

     subset_sum |      a      
------------+-------------
      59985 | {A,K,N,O,U}
      59985 | {I,K,R,T,U}
      59985 | {A,G,J,N}
      59985 | {A,F,G,P,Y}
      59985 | {C,K,O,Z}
      59985 | {A,C,F,J,O}
      59985 | {F,H,L}
      59985 | {D,E,M}
      59985 | {A,C,K,U}
      59985 | {E,J,K,M,R}
(10 rows)

    请注意，执行时间将随着基表中的行数呈指数增长。

    • 4

相关问题