Oracle 行的总重量选择

我有1000块重量在360到430克之间。我需要选择一组重量为50.000克的立方体。您是否知道如何在SQL或PL/SQL中执行此操作？

CREATE TABLE CUBES
(
  ID      VARCHAR2(100 CHAR),
  WEIGHT  NUMBER(10,3)
);

BEGIN
  FOR i IN 1..1000 LOOP
    INSERT INTO cubes VALUES (i, round(dbms_random.value( 360, 430), 3));
  END LOOP;
  COMMIT;
END;

所以你想找到权重之和50,000的所有行集？

如果是这样，请记住以下几点:

-不能保证您的数据中有这样的组!
-这是装箱问题的一种形式，它是NP完全的。这意味着没有已知的解决方案既快速又最优

如果您愿意采用一些快捷方式，则可以使用match_regnize快速轻松地找到接近的值。通过一个通过数据，你可以得到合理的接近:

select *
from   cubes match_recognize (
  measures 
    sum ( weight ) as total,
    match_number () as grp
  pattern ( total+ )
  define 
    total as sum ( weight ) <= 50000
)
order  by total desc;

TOTAL           GRP   
   49943.371      6 
   49929.287      3 
    49878.49      5 
   49785.969      4 
    49770.08      1 
   49763.964      2 
   49636.947      7 
    47082.75      8

接近，但离目标还差50个。让我们试着靠近一点。很高兴看到哪些立方体也构成了这个总数。

我们可以通过添加以下条款来解决这两个问题:

all rows per match
after match skip to next row

这意味着我们将在输出中看到每个匹配的行。并多次重访每一行，因此它可能分为多个组。

要查找总重量最接近50,000的组中的立方体，包括:

max ( grp ) keep (
 dense_rank first order by total desc
) over () max_grp

在子查询中，筛选具有与外部查询中的此max相同的组的行。给予:

with rws as ( 
  select grps.*,
         max ( grp ) keep (
           dense_rank first order by total desc
         ) over () max_grp
  from   cubes match_recognize (
    measures 
      final sum ( weight ) as total,
      match_number () as grp
    all rows per match
    after match skip to next row
    pattern ( total+ )
    define 
      total as sum ( weight ) <= 50000
  ) grps
)
  select * from rws
  where  grp = max_grp;
  
TOTAL           GRP ID         WEIGHT    MAX_GRP   
   49999.505    541 35        369.375        541 
   49999.505    541 36        367.181        541 
   ...
   49999.505    541 160       389.137        541 
   49999.505    541 161       373.928        541 

127 rows selected. 

现在我们更近了。而且查询仍然很快。但是我们每次都以相同的顺序遍历行。

我们可以看看是否可以通过首先按随机值对表进行排序来获得 (一点) 更近。然后重新运行查询几次。例如:

with crand as (
  select * from cubes
  order  by dbms_random.value
), rws as ( 
  select ...
  from   crand match_recognize (
  ...
)
  select * from rws
  where  grp = max_grp;

这仍然很快。但是，不能保证您会得到总计50k的任何团体，或者如果没有，则最接近的团体。

我不知道有什么方法可以在合理的时间范围内找到最接近的组。蛮力方法具有阶乘复杂性-即使在1,000行的小数据集上，这也令人难以置信!

其他人可能知道一些更好的算法，你可以用它来获得更准确的结果。