时间戳

首页 > 解决方案 > 查询以查找具有最大总和的最多行数

sql - 查询以查找具有最大总和的最多行数

问题描述

我有一个如下所示的表格，例如

A.    1
B.    2
C.    3
D.    99
E.    90

我需要一个查询来计算并返回总和等于或小于 102 的最大行数的集合，例如，选择总数最接近目标的集合。

如果存在具有相同总行数和相同行数的并列结果，则采用 Accessible 单个值最高的集合

在这个例子中，答案是A,B,D因为它有三个项目，而C,D（总和为 102）只有两个。

标签： sqloracleknapsack-problemsubset-sum

解决方案

您可以使用递归查询，但由于这是一个非多项式问题，性能会随着记录的增多而降低。第一个with查询只是生成示例数据。在您的情况下，您当然会查询您的实际表：

with tbl(key, value) as (
    select 'A',  1 from dual union all
    select 'B',  2 from dual union all
    select 'C',  3 from dual union all
    select 'D', 99 from dual union all
    select 'E', 90 from dual
),
rec(greatest_key, greatest_single, key_count, keys, total) as (
    select     key,
               value,
               1,
               key, 
               value
    from       tbl
    union all
    select     tbl.key,
               greatest(tbl.value, rec.greatest_single),
               rec.key_count+1,
               substr(rec.keys, 0, 1000) || ', ' || tbl.key,
               rec.total + tbl.value
    from       rec 
    inner join tbl 
            on tbl.key > rec.greatest_key
           and rec.total + tbl.value <= 102
),
ordered(total, keys, r) as (
    select   total, keys, row_number() over ( 
                          order by total desc, key_count desc, greatest_single desc)
    from     rec
)
select total, keys
from   ordered
where  r = 1

该ordered部分只是为了获得“顶级”记录。

看到它在rextester上运行。

如果您有 Oracle 12c+，则可以不使用以下命令结束查询ordered：

select   total, keys
from     rec
order by total desc, 
         key_count desc
OFFSET 0 ROWS FETCH NEXT 1 ROWS ONLY

推荐阅读