背包问题-优美的SQL讨论

最闪亮滴星

需求：
oracle数据库，表中的列有两列，分别叫datapath和bytes，datapath是表示数据文件的完整路径，bytes是表示数据文件的大小。
需要写一个select语句，
把各个bytes值组合相加，每次相加尽可能接近16000000000000 (16TB), 然后这些datapath是一类，将datapath中路径的值replace成不同值

最闪亮滴星

测试表
create table  testpath2 as (
select '/data/'as datas ,'file1' as datapath ,'9999' as bytes from dual
union
select '/data/'as datas ,'file2' as datapath ,'8999' as bytes from dual
union
select '/data/'as datas ,'file3' as datapath ,'29999' as bytes from dual
union
select '/data/'as datas ,'file4' as datapath ,'19999' as bytes from dual
union
select '/data/'as datas ,'file5' as datapath ,'29999' as bytes from dual
union
select '/data/'as datas ,'file6' as datapath ,'79999' as bytes from dual
union
select '/data/'as datas ,'file7' as datapath ,'149999' as bytes from dual
union
select '/data/'as datas ,'file8' as datapath ,'13999' as bytes from dual
union
select '/data/'as datas ,'file9' as datapath ,'129999' as bytes from dual
union
select '/data/'as datas ,'file0' as datapath ,'149999' as bytes from dual
)

最闪亮滴星

最终效果如下：
路径        文件名        16T组合大小        原始大小
/data/1        file2        152995        8999
/data/1        file4        152995        19999
/data/1        file5        152995        29999
/data/1        file6        152995        79999
/data/1        file8        152995        13999
/data/2        file0        0        149999
/data/2        file1        0        9999
/data/2        file3        0        29999
/data/2        file7        0        149999
/data/2        file9        0        129999

最闪亮滴星

为了便于观看 这里我们测试表 调整了下 ，将bytes 减少了8个0 同时定义 组合值>150000 且  组合值<160001 即为满足 接近16T的结果

最闪亮滴星

这是我的答案，坐等大佬们点评：
with v1 as (select sum_path,sum_byte ,
dbms_aw.eval_number(sum_byte) sum1，regexp_count(sum_path,'/') cnt from (
SELECT        ltrim(sys_connect_by_path(datapath, '/'), '/') AS sum_path,  
               ltrim(sys_connect_by_path(bytes, '+'), '+') AS sum_byte
          FROM testpath1  
         WHERE connect_by_isleaf = 0
        CONNECT BY nocycle PRIOR ROWID < ROWID  
        ) where dbms_aw.eval_number(sum_byte) <= 160000
        and dbms_aw.eval_number(sum_byte) > 150000 order by sum1,cnt
)
, A AS(SELECT  sum_path,sum1,rownum rn   FROM v1 ),
V2 AS (
SELECT  rn, REGEXP_SUBSTR(A.sum_path, '[^/]+', 1, QG_PURP_CD) AS STR,sum1 FROM A,
(SELECT LEVEL QG_PURP_CD   FROM DUAL
  CONNECT BY LEVEL <= (SELECT MAX(regexp_count(a.sum_path,'/') + 1)  FROM A)) B
WHERE QG_PURP_CD <=regexp_count(a.sum_path,'/') + 1)
,v4 as (
select a.rn,a.str,a.sum1 bytes ,c.bytes cbytes from v2 a,
(select min(rn) rn2 ,str from v2 group by  str) b,testpath1 c where a.rn=b.rn2 and a.str=b.str  and a.str=c.datapath  )
,v5 as (
select a.rn ,  str datapath，bytes  ,cbytes  from v4 a where rn in
(select rn from (select sum(cbytes)cbytes ,rn from v4 group by rn) where cbytes<=160000
and cbytes> 150000
) order by a.rn,a.str)
,v6 as (
select rn,rownum rm from (select rn,wm_concat(datapath) from v5 group by rn))
,v7 as (
select '/data/'||v6.rm 路径, v5.datapath 文件名 ,v5.bytes as "16T组合大小",v5.cbytes as 原始大小  from v5 ,v6 where v5.rn=v6.rn
UNION
select '/data/'||(select max(rm)+1 from v6) ,datapath,0,bytes  from testpath1 where datapath not in (select datapath from v5 )
)
select * from v7

newkid

那我就老实不客气开始点评了：


WITH
    v1 AS (
        SELECT sum_path,
                sum_byte,
                dbms_aw.eval_number (sum_byte) sum1
               ,regexp_count(sum_path,'/') cnt
          from (
            SELECT ltrim(sys_connect_by_path(datapath, '/'), '/') AS sum_path,
                   ltrim(sys_connect_by_path(bytes, '+'), '+') AS sum_byte
              FROM testpath1
            WHERE connect_by_isleaf = 0
            CONNECT BY nocycle PRIOR ROWID < ROWID
           )
       where dbms_aw.eval_number(sum_byte) <= 160000
        and dbms_aw.eval_number(sum_byte) > 150000
       order by sum1,cnt
       )
----- 这个V1是要找出所有组合并且求和。这个connect_by_isleaf = 0不知道何用，万一所有的物品都不够装一袋呢?
----- 这个 > 150000 条件也是毫无道理的，V1结果会被后面用来分组，这个筛选条件可能会漏掉答案
----- 这个步骤其实是很暴力的，如果物品很多，它会所有组合都尝试一遍，这是经典的背包问题算法所要避免的

, A AS(SELECT  sum_path,sum1,rownum rn   FROM v1 )
----- 这一步看来就是利用v1的排序求出rownum, 可以合并到V1里面改用row_number()

,V2 AS (
SELECT rn,
       REGEXP_SUBSTR (A.sum_path,
                      '[^/]+',
                      1,
                      QG_PURP_CD)
           AS STR,
       sum1
  FROM A,
       (    SELECT LEVEL QG_PURP_CD
              FROM DUAL
        CONNECT BY LEVEL <=
                   (SELECT MAX (REGEXP_COUNT (a.sum_path, '/') + 1) FROM A)
       ) B
WHERE QG_PURP_CD <= REGEXP_COUNT (a.sum_path, '/') + 1
)
--------- 这一步是把V1里面的路径打算还原成每个物品一行，rn是组合的编号

,v4 AS (
SELECT a.rn,
       a.str,
       a.sum1  bytes,
       c.bytes cbytes
  FROM v2         a,
       (  SELECT MIN (rn) rn2, str
            FROM v2
        GROUP BY str) b,
       testpath1  c
WHERE a.rn = b.rn2 AND a.str = b.str AND a.str = c.datapath
  )
-------- 这一步是要求出每个物品最早出现在哪一组。和c连接是为了获得这个物品单独的重量。
-------- 这个V4的设计已经出现问题了，为什么选择最 小的一组?

,v5 AS (
  SELECT a.rn, str datapath，bytes, cbytes
    FROM v4 a
   WHERE rn IN (SELECT rn
                  FROM (  SELECT SUM (cbytes) cbytes, rn
                            FROM v4
                        GROUP BY rn)
                 WHERE cbytes <= 160000 AND cbytes > 150000)
ORDER BY a.rn, a.str
)
--------- V4已经是还原到每个物品一行，里面还有一些同组的，再进行求和，然后总和太小的就丢弃。这个也看不出什么道理。 order by没用

,v6 as (
select rn,rownum rm from (select rn,wm_concat(datapath) from v5 group by rn))
--------- wm_concat没用。这个v6的计算可以合并到V5, 在 GROUP BY rn 之后就可以求 rownu, 然后 inner join v4 而不是用in


,v7 as (
select '/data/'||v6.rm 路径, v5.datapath 文件名 ,v5.bytes as "16T组合大小",v5.cbytes as 原始大小  from v5 ,v6 where v5.rn=v6.rn
UNION
select '/data/'||(select max(rm)+1 from v6) ,datapath,0,bytes  from testpath1 where datapath not in (select datapath from v5 )
)
select * from v7

------ 你把前面挑剩下的全部归为一组放在union，造成下面这个结果：
/data/2        file0        0        149999
/data/2        file1        0        9999
/data/2        file3        0        29999
/data/2        file7        0        149999
/data/2        file9        0        129999


这并不是楼主想要的。楼主是尽量拼凑16T一组，最后剩下的再凑一组，总和也是要满足 <=16T的条件。

newkid

以前这里有过一些背包问题的讨论：
http://www.kz486.com/viewthread. ... ;extra=#pid14180585
http://www.kz486.com/thread-1291806-1-1.html

第二帖的原帖被缺德的楼主给删了，不过从我的回复还是可以看出一些有价值的东西。


回到楼主这个题，用暴力法玩了一下：

with d as (
---------- 每个物品用二进制一位表示，这是为了在求分组的时候，避免每个组合之间有重复的成员。ORACLE的NUMBER可以支持125位，就是小规模数据玩玩而已
select power(2,rownum) bit, datapath, bytes from testpath1
)
,grp(bits,bytes,last_bit,cnt) as (
------ 暴力法求出所有组合
select bit,bytes,bit,1 from d
union all
select grp.bits+d.bit,grp.bytes+d.bytes,d.bit,grp.cnt+1 from grp,d where grp.last_bit<d.bit and grp.bytes+d.bytes<=160000
)
,t(bits,cnt,last_bits,total_cnt,found,path,rn) as (
----- 开始拼凑这些组合，看看哪种拼法能够用最少的组凑齐所有物品
select bits,cnt,bits,(select count(*) from d),0,cast(bits as varchar2(1000)),1 from grp
union all
select t.bits+grp.bits,t.cnt+grp.cnt,grp.bits,t.total_cnt
      ,count(case when t.cnt+grp.cnt=t.total_cnt then 1 end) over()
      ,t.path||','||grp.bits
      ,row_number() over(partition by t.bits+grp.bits order by 1) rn ----- 这是一点点优化，如果组成员有互换的，其实不会影响最后总组数，所以只需留下一种
from t,grp
where t.bits<grp.bits and bitand(t.bits,grp.bits)=0 and t.cnt+grp.cnt<=t.total_cnt and t.found=0 and t.rn=1
)
,r as (
select to_number(regexp_substr(path,'[^,]+',1,level)) bit
      ,level grp_id
  from (select * from t where cnt=total_cnt and rownum=1)
connect by level<=regexp_count(path,',')+1
)
select listagg(d.datapath,',') within group(order by d.datapath)
      ,sum(d.bytes)
  from r,d
where bitand(r.bit,d.bit)>0
group by r.grp_id;

分组方法可能有很多，答案也不是**的，这是我这里跑出来的答案：
file0        149999
file3,file4,file5,file6        159996
file1,file7        15999 8
file2,file8,file9        152997

要为每组加上**的组号变成路径就很简单了, 这边没有写出来。

jlandzpa

看到“ > 150000” 的条件 ，就知道语句不具备普适性。

newkid

jlandzpa 发表于 2023-3-12 20:01
看到“ > 150000” 的条件 ，就知道语句不具备普适性。

哇！江局！什么春风吧老领导吹来了？

jlandzpa

newkid 发表于 2023-3-13 01:00
哇！江局！什么春风吧老领导吹来了？

我是过来学习的