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

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

前面几篇都是通过SQL的方式求解，这里尝试使用PL/SQL实现。

一个复杂问题的求解过程（一）：http://yangtingkun.itpub.net/post/468/456641

一个复杂问题的求解过程（二）：http://yangtingkun.itpub.net/post/468/456695

一个复杂问题的求解过程（三）：http://yangtingkun.itpub.net/post/468/456778

在第一篇文章中就提到了，这个算法的实现使用PL/SQL会比用SQL实现容易一些，不过今天尝试完全使用PL/SQL实现，发现也不是想象中那样简单。

由于SQL和PL/SQL的实现思路是完全不同的，这里尽量避免受前面SQL方法的影响，而选择了全表通过PL/SQL实现。

另外，提出这个问题的wangfans给出了递归方式的实现，这里就尝试采用循环的实现方式，通过一个存储过程直接获得答案。

SQL> CREATE OR REPLACE PROCEDURE P_RESULT ASITPUB个人空间Z^G|q,o"^X#~
  2   TYPE T_VARRAY IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
S9u4}5a/[;X0  3   TYPE T_VAR_VAR IS TABLE OF T_VARRAY INDEX BY BINARY_INTEGER;
#x$W IU e\Es0  4   TYPE T_VARCHAR2_VAR IS TABLE OF NUMBER INDEX BY VARCHAR2(20);ITPUB个人空间-Vss1f9flD/ih-me
  5   TYPE T_VARCHAR2_VAR_TAB IS TABLE OF T_VARCHAR2_VAR INDEX BY BINARY_INTEGER;ITPUB个人空间2](hrQ8qUaG2n
  6   V_TAB T_VAR_VAR;ITPUB个人空间8x7|gf0nt!b?)Y
  7   V_SUM T_VARCHAR2_VAR_TAB;ITPUB个人空间9ix^ m1`#R CN
  8   J VARCHAR2(20);
,VK+zj+h]FQK
~0  9  BEGIN
ylp8SWS0o3d.}A g0 10   FOR I IN (SELECT ID, VALUE, POWER FROM T ORDER BY 1) LOOPITPUB个人空间QV+d
r-u?Ge3@
 11    FOR K IN 0..I.POWER - 1 LOOPITPUB个人空间fic(l0A.r^
 12     V_TAB(I.ID)(K) := I.VALUE * K;ITPUB个人空间4F.EDtXFWq
 13    END LOOP;ITPUB个人空间G8k#w![HU|S5\
 14    IF I.ID = 1 THEN
_+ff0P IZ}e0 15     FOR K IN V_TAB(1).FIRST..V_TAB(1).LAST LOOP
u+IV8zv4H8A9\+Mf0 16      V_SUM(1)(K) := V_TAB(1)(K);ITPUB个人空间pxL\j)W
 17     END LOOP;ITPUB个人空间|QEILPd
 18    ELSE
v'{1^Z;q6lC&Di0 19     J := V_SUM(I.ID - 1).FIRST;
U/{!G.`$r0 20     WHILE (V_SUM(I.ID - 1).EXISTS(J)) LOOP
&^*X(Bb3I/N`3[/{,}0 21      FOR K IN V_TAB(I.ID).FIRST..V_TAB(I.ID).LAST LOOPITPUB个人空间)}9D
sts8wkr^
 22       V_SUM(I.ID)(J || ',' || TO_CHAR(K)) := V_SUM(I.ID - 1)(J) + V_TAB(I.ID)(K);ITPUB个人空间l@*GO"j{b u
 23       IF V_SUM(I.ID)(J || ',' || K) > 16 THENITPUB个人空间UVi#^Uw$]"{7pA i4W
 24        V_SUM(I.ID).DELETE(J || ',' || K);ITPUB个人空间;n$d9F5aSg
 25       END IF;
1lq(z|*V0 26      END LOOP;
[2c |h8~0 27      J := V_SUM(I.ID - 1).NEXT(J);ITPUB个人空间Em/F*q]7[5](h
 28     END LOOP;
Q]-z3F$D6Q{q0 29    END IF;ITPUB个人空间Acq(d@t
 30   END LOOP;
NR-_ DF)rN0 31   FOR I IN (SELECT MAX(ID) ID FROM T) LOOPITPUB个人空间2Dx%]f9B#m*t
 32    J := V_SUM(I.ID).FIRST;ITPUB个人空间$i2A8D)A%^x
 33    WHILE (V_SUM(I.ID).EXISTS(J)) LOOP
5Dde |'k-]*` w*T5Bx0 34     IF V_SUM(I.ID)(J) = 16 THEN
@^~djn:b0 35      DBMS_OUTPUT.PUT_LINE(J);ITPUB个人空间3lqh~~}#A&S
 36     END IF;
v4G*PR4V;g2i0 37     J := V_SUM(I.ID).NEXT(J);
T/~(l'}T+N0 38    END LOOP;ITPUB个人空间"T0zZ"{(n.K"U%C
 39   END LOOP;
!w*X5X:\d$m0 40  END;ITPUB个人空间+dv MNa
bW'N
 41  /

过程已创建。

SQL> SET SERVEROUT ON
DY9Kja3SL0SQL> EXEC P_RESULTITPUB个人空间"N0@BHm*ww)q4A
0,0,2,0,2
s%Qm([V?00,0,3,0,1ITPUB个人空间2z@k]'V
1,1,0,1,2
'r:w^}:Y;M ?8h.s*i01,1,1,1,1ITPUB个人空间"}MEDNT7yT!w
1,1,2,1,0ITPUB个人空间C,Q-x:G-r\I(L3?
2,0,1,0,2ITPUB个人空间)l*wu!F.i6E\ K
2,0,2,0,1ITPUB个人空间O"r6`7KXJ(V:l
2,0,3,0,0

PL/SQL过程已成功完成。

过程中利用一个二维数组保存ID对应的加权与VALUE乘积的可能性。并建立了另一个二维数组，保存最终的汇总值。这个二维数组其中一个维度不是数值，而是字符串类型，且这个字符串中保存的值，就是需要计算的各个加权值列表。

采用这个方法效率应该还是相对比较高的，不过由于定义了两个二维数组，空间占用可能会相对大一些。