求一超难存储过程

newkid

1. 会花很多时间，就像死了一样。
2. 可以改一下程序，等我有空

newkid

求最接近的解：
declare
   type test_t is table of vw_money%rowtype index by binary_integer;
   res test_t;
   l_row binary_integer:=1;
   sums number;
   cal varchar2(1000);
   seq varchar2(1000);
   j NUMBER;
   lv_result NUMBER;
   lv_target NUMBER := 33;
   lv_cal VARCHAR2(1000);
   lv_seq VARCHAR2(1000);
begin

  SELECT *
  BULK COLLECT INTO res
  FROM vw_money;
  
  --dbms_output.put_line(res.count);
  lv_result := NULL;
  for i in res.first .. 2**res.last-1 loop
      sums:=0;
      seq:='';
      cal:='';
      j:=1;
      WHILE j<=res.count AND res(j).pow<=i LOOP
       if (bitand(i,res(j).pow) <> 0) then  -- 2的幂事先算好了
         sums:=sums+res(j).amount;
         cal:=cal||res(j).amount||'+';
         seq:=seq||res(j).id||',';   
         IF sums - lv_target >= ABS(lv_result - lv_target) THEN        ---- 已经有更接近的答案
            EXIT;
         END IF;
       end if;
       j:=j+1;
      end loop;
      IF lv_result IS NULL OR ABS(sums - lv_target) < ABS(lv_result - lv_target) THEN
         lv_result := sums;
         lv_cal := cal;
         lv_seq := seq;
      END IF;
      IF lv_result = lv_target THEN
         EXIT;
      END IF;
  end loop;
  
  lv_cal:=substr(lv_cal,1,length(lv_cal)-1);
  lv_seq:=substr(lv_seq,1,length(lv_seq)-1);
  dbms_output.put_line('结果是:'||lv_cal||'='||lv_result);
  dbms_output.put_line('序列是:'||lv_seq);

end;
/

newkid

改一下nyfor的解法求最接近答案：

create or replace package hierarchy is
  type strtabletype1 is table of varchar2(4000) index by binary_integer;
  type strtabletype is table of strtabletype1 index by binary_integer;
  
  strtable strtabletype;
  
  type numtabletype1 is table of number index by binary_integer;
  type numtabletype is table of numtabletype1 index by binary_integer;
  
  numtable numtabletype;
  function sys_connect_by_path(p_level     in number,
                               p_value     in varchar2,
                               p_delimiter in varchar2 default ',',
                               p_index     IN NUMBER DEFAULT 1)
    return varchar2;
  function sys_sum_by_path(p_level in number, p_value in number,p_index     IN NUMBER DEFAULT 1)
    return number;
  pragma restrict_references(sys_connect_by_path, wnds);
  pragma restrict_references(sys_sum_by_path, wnds);
  
  lv_target NUMBER;
  lv_found NUMBER;
  
  PROCEDURE reset(p_target IN NUMBER);

  FUNCTION if_continue(p_level in number, p_value in number,p_index IN NUMBER DEFAULT 1)
    return number;

end;
/

create or replace package body hierarchy is

  ls_ret varchar2(4000);
  ln_ret number;
  function sys_connect_by_path(p_level     in number,
                               p_value     in varchar2,
                               p_delimiter in varchar2 default ',',
                               p_index     IN NUMBER DEFAULT 1)
    return varchar2 is
  begin
    strtable(p_index)(p_level) := p_value;
    ls_ret := p_value;
    for i in reverse 1 .. p_level - 1 loop
      ls_ret := strtable(p_index)(i) || p_delimiter || ls_ret;
    end loop;
    return ls_ret;
  end;

  function sys_sum_by_path(p_level in number, p_value in number,p_index     IN NUMBER DEFAULT 1)
    return number is
  begin
    numtable(p_index)(p_level) := p_value;
    ln_ret := p_value;
    for i in reverse 1 .. p_level - 1 loop
      ln_ret := numtable(p_index)(i) + ln_ret;
    end loop;
    return ln_ret;
  end;

  PROCEDURE reset(p_target IN NUMBER)
  AS
  BEGIN
     lv_target := p_target;
     lv_found := 0;
  END reset;
  
  FUNCTION if_continue(p_level in number, p_value in number,p_index IN NUMBER DEFAULT 1)
  RETURN NUMBER
  IS
     lv_current NUMBER;
  BEGIN
     IF lv_found=1 THEN
        RETURN 0;
     END IF;
     lv_current := sys_sum_by_path(p_level, p_value,p_index);
     IF lv_current<lv_target THEN
        RETURN 1;
     ELSE
        IF lv_current=lv_target THEN
           lv_found :=1;
        END IF;
        RETURN 0;
     END IF;
  END if_continue;
end;
/

---- 运行SQL之前必须初始化，设入目标答案(注意每次运行之前都要设，因为涉及到全局标志的初始化。否则会有奇怪的答案)：
EXEC hierarchy.reset(33);

select path,amounts,total_amount from (
select rownum rn,
               sys_connect_by_path(id, ',') path,
               hierarchy.sys_connect_by_path(level, amount, '+') amounts,
               hierarchy.sys_sum_by_path(level, amount) total_amount
          from t_money
        connect by id > prior id
               AND hierarchy.if_continue(level, amount)=1
order by abs(total_amount-33)
)
where rownum=1;

[ 本帖最后由 newkid 于 2009-9-1 03:12 编辑 ]

nyfor

原帖由 newkid 于 2009-9-1 02:14 发表
改一下nyfor的解法求最接近答案：.............

呵呵,newkid 真是"敬业"啊(一下子不知道该用什么词了,这不是工作,用敬业二字不太合适哈).
其实我的解法没啥用的,就是想到一个利用 hierarchy 来进行穷举罢了.

newkid

呵呵你也太拔高我了，其实就是吃饱了撑的。

dhhb

for i in res.first .. 2**res.last-1 loop
老大们能否解释为何不是 for i in 1 .. 2**res.last-1 loop

newkid

原帖由 dhhb 于 2009-9-1 10:38 发表
for i in res.first .. 2**res.last-1 loop
老大们能否解释为何不是 for i in 1 .. 2**res.last-1 loop

res.first =1
两个是一回事，直接写1也可以。

郭清明

现在，用户要求容差必须有个范围，比如  1或者-1   金额是32块钱，   如果找不到 32 可以找到 31或者33，如果容差范围内的数都找不到的话，返回结果：找不到符合条件的组合。
最好用“for i in res.first .. 2**res.last-1 loop”这个算法修改，因为nyfor的解法我还没能完全理解，你上次帮我改的方法中能求到最接近的组合，但能加个范围就好，而且，容差和总金额数一样能作为输入参数，这样用户可以修改容差范围。

前辈有空再帮我小改下。
谢谢。

newkid

declare
   type test_t is table of vw_money%rowtype index by binary_integer;
   res test_t;
   l_row binary_integer:=1;
   sums number;
   cal varchar2(1000);
   seq varchar2(1000);
   j NUMBER;
   lv_result NUMBER;
   
   lv_target NUMBER := 33;     --- 目标
   lv_diff   NUMBER := 2;      --- 允许误差
   
   lv_cal VARCHAR2(1000);
   lv_seq VARCHAR2(1000);
begin

  SELECT *
  BULK COLLECT INTO res
  FROM vw_money;
  
  --dbms_output.put_line(res.count);
  lv_result := NULL;
  for i in res.first .. 2**res.last-1 loop
      sums:=0;
      seq:='';
      cal:='';
      j:=1;
      WHILE j<=res.count AND res(j).pow<=i LOOP
       if (bitand(i,res(j).pow) <> 0) then  -- 2的幂事先算好了
         sums:=sums+res(j).amount;
         cal:=cal||res(j).amount||'+';
         seq:=seq||res(j).id||',';   
         IF sums - lv_target >= ABS(lv_result - lv_target) OR sums - lv_target>lv_diff THEN        ---- 已经有更接近的答案或误差超出范围
            EXIT;
         END IF;
       end if;
       j:=j+1;
      end loop;

      IF ABS(sums - lv_target)<=lv_diff AND (lv_result IS NULL OR ABS(sums - lv_target) < ABS(lv_result - lv_target)) THEN
         lv_result := sums;
         lv_cal := cal;
         lv_seq := seq;
      END IF;
      IF lv_result = lv_target THEN
         EXIT;
      END IF;
  end loop;

  IF lv_result IS NULL THEN
     dbms_output.put_line('不存在符合要求的答案');
  ELSE
   
     lv_cal:=substr(lv_cal,1,length(lv_cal)-1);
     lv_seq:=substr(lv_seq,1,length(lv_seq)-1);
     dbms_output.put_line('结果是:'||lv_cal||'='||lv_result);
     dbms_output.put_line('序列是:'||lv_seq);
  END IF;
  
end;
/

郭清明

前辈，这道题目还有一个终极BT的需求，不知道能否实现：假设现在表里面只有这样3条记录，如下图所示：
truncate table t_money;
insert into t_money values(1,5);
insert into t_money values(2,7);
insert into t_money values(3,7);
id            amount     
----------------------
1        5
2        7
3        7
-----------------------

所求总金额是10，容差是1 ，当所选组合大于容差范围的时候，拆分当前的记录的金额，使得拆分的金额+之前所选的金额总数=所求金额数，算法举例：   5+7=12，  12-10=2   ，2>1 不满足容差范围，所以拆分7，7=5+2，所以，得到5+5=10，  序列组合为 1，2     其中序列号为2 的记录有2元作为余额（余额不保存，只保存已选取金额），因此最终的结果仍然只要返回5+5=10，满足要求的组合的序列号为1，2就可以了。
谢谢。