一个复杂问题的求解过程（一）

今天在PUB里面看到一个帖子：http://www.itpub.net/thread-949571-1-1.html。问题本身并不复杂，不过想借这个问题简单描述一下求解的思路。

首先建立测试用表：

SQL> CREATE TABLE T (ID NUMBER, VALUE NUMBER, POWER NUMBER);

表已创建。

SQL> INSERT INTO T VALUES (1, 2, 3);

已创建1行。

SQL> INSERT INTO T VALUES (2, 1, 2);

已创建1行。

SQL> INSERT INTO T VALUES (3, 4, 4);

已创建1行。

SQL> INSERT INTO T VALUES (4, 5, 2);

已创建1行。

SQL> INSERT INTO T VALUES (5, 4, 3);

已创建1行。

SQL> COMMIT;

提交完成。

由于楼主对于问题描述的不是很清晰，这里再简单描述一下。表中有三列，第一列是表的ID，第二列是一个ID对应的因子。而第三列是第二列值加权的上限。

以第一条记录为例，这条记录对应的因子是2，最大加权小于3，也就是说，这条记录可以对应三个值，0、2、4分布对应POWER列的加权值为0、1、2。

现在根据配置表中给出的因子和每个因此的最大加权范围，找出因子加权后的总和为16时，所对应的所有加权值的情况。

一个简单的例子：每个加权值都是1的话，总和就是16，因此这就是所求的一种情况。

SQL> SELECT 2*1 + 1*1 + 4*1 + 5*1 + 4*1 FROM DUAL;

2*1+1*1+4*1+5*1+4*1ITPUB个人空间!]s1@ |m$_o
-------------------
8a-rtZ5C0                 16

同理，2/0/3/0/0也是一种情况：

SQL> SELECT 2*2 + 1*0 + 4*3 + 5*0 + 4*0 FROM DUAL;

2*2+1*0+4*3+5*0+4*0
n.H T V&z"Y0-------------------
KD/Gh*D6c#d'`9[A0~0                 16

而2/0/0/0/3虽然相加的结果也是16，但是对于ID为5的记录，加权必须小于3，因此这组加权值是不正确的。

了解了需求就可以选择方法了，这种问题通过PL/SQL的过程性语言来实现要容易一些，这里尝试使用SQL来实现。

下面分析需求，SQL最终要实现的是一组乘积的和，并过滤和为16的结果。如何得到乘积是比较困难的，由于表中只给出了最大加权范围，因此需要通过构造的方式，获取到因子和所有可能加权的乘积。

为了构造出连续的数值，一般通过CONNECT BY ROWNUM <数值的方式来实现，但是对于目前的情况，需要对多个多组记录分别构造，而直接使用CONNECT BY ROWNUM会造成大量的重复结果，因此这里选择了使用子查询作为列的方式来避免重复记录的出现。但是构造的加权结果一般都大于1条，对于子查询作为列的方式只能返回一条记录，这里使用了聚集函数MAX配合属性查询的SYS_CONNECT_BY_PATH来实现。

SQL> SELECT ID, VALUE,
1p&SfZ6Z e8E}7i0  2   (ITPUB个人空间q*|F0C-C D
  3    SELECT MAX(SYS_CONNECT_BY_PATH(VALUE * (LEVEL - 1), ','))ITPUB个人空间B"h+E
Ajs
  4    FROM DUAL CONNECT BY ROWNUM <= POWERITPUB个人空间.`[6H?F[N?S8|
  5   ) POWER
+K+?0H
XZfc)L0  6  FROM TITPUB个人空间dq2A `%gw`!a2m
  7  ;

        ID      VALUE POWERITPUB个人空间 |0x2ay.}`
---------- ---------- ------------------------------
be}&uANxP0         1          2 ,0,2,4
L A:@)r bs r-X0         2          1 ,0,1
cQ4L3P#D~0         3          4 ,0,4,8,12ITPUB个人空间"im'gjHm0@x)h
         4          5 ,0,5ITPUB个人空间c9~"n@1S;~PV1dE
         5          4 ,0,4,8

现在已经获得了加权的列表，需要通过SQL将其展开。最简单的思路就是通过5个SQL，获取每一个ID所有可能的因子加权乘积。

将5个SQL关联起来，计算乘积的和，并过滤结果为16的情况，就可以得到最终结果了。

SQL> WITH T1 ASITPUB个人空间V N{:|3DKF
  2  (
8i/U.k[*}G0  3  SELECT ID, VALUE,ITPUB个人空间)\)F4^/{1Nu
  4   (
@ \5kV'_0  5    SELECT MAX(SYS_CONNECT_BY_PATH(VALUE * (LEVEL - 1), ','))
Mq n-h$A dF)u0  6    FROM DUAL CONNECT BY ROWNUM <= POWER
Z&|1r K0?5}:Z&r ?+Hp.}+m0  7   ) POWERITPUB个人空间6{ShbO f,o
  8  FROM T
\.S6@1{:EY0  9  )
O|,f2K~;b0 10  SELECT LEVEL - 1 LV,ITPUB个人空间HCb-HZ)u8Y(Y
 11   SUBSTR(POWER,
T\"bi"Wd0 12    INSTR(POWER, ',', 1, ROWNUM) + 1,ITPUB个人空间3h`;vA7f:f4K.P(U
 13    INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
!H-n:uA2b!_)`7O~0 14  FROM (SELECT * FROM T1 WHERE ID = 1)ITPUB个人空间a:u y1o.`6C%N
 15  CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','));

       LVVALUEITPUB个人空间q"^7qR2yR1W)^3X
---------- ------------------------------ITPUB个人空间g5d/@ zT J ewa^s
         0 0ITPUB个人空间0Z jFjD
         1 2ITPUB个人空间0F~-Jv"a
         2 4

这就是获取ID为1的所有加权因子乘积的SQL。

只需要将5个SQL关联并求和，就可以得到最终的结果：

SQL> WITH T1 ASITPUB个人空间
izd,]
h&PD
  2  (ITPUB个人空间H}4e{y(Q%b4tV
  3  SELECT ID, VALUE,
+z+[$Ku*L0  4   (
#`o:_6s0oo0  5    SELECT MAX(SYS_CONNECT_BY_PATH(VALUE * (LEVEL - 1), ','))
qhk#Ac o/It0  6    FROM DUAL CONNECT BY ROWNUM <= POWERITPUB个人空间 }3K8w'm S@Hb_
  7   ) POWERITPUB个人空间 m3[5LD X/{y$dx
  8  FROM TITPUB个人空间x[v!@j
  9  )ITPUB个人空间1UxS g$L8Ox
 10  SELECT L1, L2, L3, L4, L5ITPUB个人空间] ]7[
S'OZ,u6@
 11  FROM
%b^O Zra2i:kV0u0 12  (ITPUB个人空间(d4}|.d5~sO!p
 13   SELECT A.LV L1, B.LV L2, C.LV L3, D.LV L4, E.LV L5,
9Va3A1RI7|0 14    A.VALUE + B.VALUE + C.VALUE + D.VALUE + E.VALUE TOTALITPUB个人空间tZ }W/eZ
 15   FROM
/fx9RW@$]}0 16   (ITPUB个人空间!S,rN7E#[J,v
 17    SELECT LEVEL - 1 LV,
;Me3xvV$@].d0C0 18     SUBSTR(POWER,
-kx PE8U fr0 19      INSTR(POWER, ',', 1, ROWNUM) + 1,
@.Bt+RxOnRU0 20      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUEITPUB个人空间GB s{.?VX:~c q
 21    FROM (SELECT * FROM T1 WHERE ID = 1)ITPUB个人空间m9fT8g\
 22    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))
:{w*mz7j2u0 23   ) A,ITPUB个人空间Z-d/K8Y(f:w&F2g|
 24   (
-qP`yX T`|"U%A {0 25    SELECT LEVEL - 1 LV,
!O:Zg4O+YIf?B _0 26     SUBSTR(POWER,
j
G2[4P
oW1G0 27      INSTR(POWER, ',', 1, ROWNUM) + 1,
fP*Y}R+_-A3X9K6V0 28      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUEITPUB个人空间 w WM1_"S
 29    FROM (SELECT * FROM T1 WHERE ID = 2)ITPUB个人空间9KQy;sNW`E
 30    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))
Q2BY+q_{
p,yJ/szS0 31   ) B,
5v(f VHtU0 32   (
jL_;u0T$F#fW&YX+c RD0 33    SELECT LEVEL - 1 LV,
FF h
V4^c%Kf0 34     SUBSTR(POWER,ITPUB个人空间!q:D
i`bP"O]b
 35      INSTR(POWER, ',', 1, ROWNUM) + 1,ITPUB个人空间)_mx4n-mG+U(cpe
 36      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
FTr"o9]/` iA0 37    FROM (SELECT * FROM T1 WHERE ID = 3)
oV6Y |b.L2^"_u0 38    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))ITPUB个人空间O'^8L9j&g,x} qS
 39   ) C,ITPUB个人空间wb#MX_+N
 40   (ITPUB个人空间"PC[/s~Sz#b
G
 41    SELECT LEVEL - 1 LV,ITPUB个人空间 u5b$M0@DfF
 42     SUBSTR(POWER,ITPUB个人空间
JgN@$fG
 43      INSTR(POWER, ',', 1, ROWNUM) + 1,
/L1_
i/rn)w0 44      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
-x?5e ae}S8y0 45    FROM (SELECT * FROM T1 WHERE ID = 4)
Xv(W&b-LZfx%y4T0 46    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))ITPUB个人空间7_2_B"lO8}r.FiQ"M
 47   ) D,
2q"ZYP df0 48   (ITPUB个人空间'dB7I
I9Az[~eh
 49    SELECT LEVEL - 1 LV,
pnA5j Ki
gW0 50     SUBSTR(POWER,
I\jhk%c aX0 51      INSTR(POWER, ',', 1, ROWNUM) + 1,ITPUB个人空间2h!z&hy3]#R|%G
 52      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUEITPUB个人空间*P?9?,WcwL3O
 53    FROM (SELECT * FROM T1 WHERE ID = 5)ITPUB个人空间` nAI6r](s3y0l
 54    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))
4_ l vUFV!? t0 55   ) E
!w$_
@)Y6T$[;G-I0 56  )ITPUB个人空间+To!HpL2{
 57  WHERE TOTAL = 16;

        L1         L2         L3         L4         L5
8R(g gl(DZ#b0---------- ---------- ---------- ---------- ----------ITPUB个人空间R%X{q3B&TLaj
         0          0          2          0          2
d3I*Qo8oD0         0          0          3          0          1ITPUB个人空间zf pg}S
         1          1          0          1          2
*N+ayo'_ OF_0         1          1          1          1          1
#aA:{!b\ |A0         1          1          2          1          0ITPUB个人空间'~B4]dg+XH
         2          0          1          0          2ITPUB个人空间D.T"@&I(R:kYL
         2          0          2          0          1ITPUB个人空间 t't$DF'xb.D2u0e
         2          0          3          0          0

已选择8行。

至此，通过硬编码式的SQL得到了最终的结果。