求一超难存储过程

fengzj

xuexi

郭清明

原帖由 郭清明 于 2009-9-3 19:54 发表
前辈，这道题目还有一个终极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就可以了。
谢谢。

拆分的前提条件是：找遍了所有的数据都没有满足要求的时候才进行拆分。

newkid

原帖由 郭清明 于 2009-9-3 21:35 发表


拆分的前提条件是：找遍了所有的数据都没有满足要求的时候才进行拆分。

多出来可以拆分，如果不足呢？

郭清明

如果所有的数据的金额加起来都不足所求金额，就返回“无符合条件的组合”

郭清明

原帖由 郭清明 于 2009-9-3 22:41 发表
如果所有的数据的金额加起来都不足所求金额，就返回“无符合条件的组合”

在实际应用中，基本不存在不足的情况，只有多，没有少的。

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 := 10;     --- 目标
   lv_diff   NUMBER := 2;      --- 允许误差
   
   lv_cal VARCHAR2(1000);
   lv_seq VARCHAR2(1000);
   
   lv_close NUMBER;
   
begin

  SELECT *
  BULK COLLECT INTO res
  FROM vw_money;
  
  --dbms_output.put_line(res.count);
  lv_result := NULL;
  lv_close := 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;
      ELSIF lv_result IS NULL AND sums - lv_target>lv_diff AND (lv_close IS NULL OR sums<lv_close) THEN
         lv_close := 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
     IF lv_close IS NULL THEN
        dbms_output.put_line('不存在符合要求的答案');
     ELSE
        lv_cal:=substr(lv_cal,1,length(lv_cal)-1)||'-'||(lv_close-lv_target);
        lv_seq:=substr(lv_seq,1,length(lv_seq)-1);
        dbms_output.put_line('结果是:'||lv_cal||'='||lv_target);
        dbms_output.put_line('序列是:'||lv_seq);

     END IF;
  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;
/

[ 本帖最后由 newkid 于 2009-9-3 22:56 编辑 ]

grubbyoo

create view  tt0 as  
select   1 id,     2 amount from dual union all
select    2 ,     2 amount from dual union all
select    3 ,      3  amount from dual union all
select    4 ,      5  amount from dual union all
select    5 ,     2  amount from dual union all
select    6 ,     8  amount from dual union all
select    7 ,     1  amount from dual union all
select    8 ,     2  amount from dual union all
select    9 ,      3  amount from dual union all
select   10 ,     3  amount from dual  

;

create view  tt1 as  
select  * from tt0
;


create view  ttall as  
select  * from tt0
;



declare
  n number := 1;
  m number := 0;
  
  x_amount number:=700;--------需要计算的值
begin

  while (m = 0) loop
  
    execute immediate ('create or replace view ttall as
                     select tts.id ||''-''|| tt0.id id ,tts.amount+ tt0.amount amount
                     from
                       (select min(id ) id ,amount  
                        from   tt' || n || '
                        group by amount ) tts,tt0
                     where tts.amount<'|| x_amount);
                     
    execute immediate ('create or replace view tt' || to_char(n + 1) ||
                      ' as
                     select tts.id ||''-''|| tt0.id id ,tts.amount+ tt0.amount amount
                     from
                     (select min(id ) id ,amount  
                     from
                     tt' || n || '
                     group by amount ) tts,tt0
                      where tts.amount<'|| x_amount);
    n := n + 1;
    select count(1) into m from ttall where amount = x_amount;
  end loop;

  for cur in (select id from ttall where amount = x_amount) loop
    dbms_output.put_line(cur.id);
  end loop;

end;

[ 本帖最后由 grubbyoo 于 2009-9-5 09:18 编辑 ]

newkid

原帖由 grubbyoo 于 2009-9-4 13:07 发表
create view  tt0 as  
select   1 id,     2 amount from dual union all
select    2 ,     2 amount from dual union all
select    3 ,      3  amount from dual union all
select    4 ,      5  amount from dual union all
select    5 ,     2  amount from dual union all
select    6 ,     8  amount from dual union all
select    7 ,     1  amount from dual union all
select    8 ,     2  amount from dual union all
select    9 ,      3  amount from dual union all
select   10 ,     3  amount from dual  

;

create view  tta1 as  
select  * from tt0
;


create view  ttall as  
select  * from tt0
;



declare
  n number := 1;
  m number := 0;
  
  x_amount number:=700;--------需要计算的值
begin

  while (m = 0) loop
  
    execute immediate ('create or replace view ttall as
                     select tts.id ||''-''|| tt0.id id ,tts.amount+ tt0.amount amount
                     from
                       (select min(id ) id ,amount  
                        from   tt' || n || '
                        group by amount ) tts,tt0
                     where tts.amount

您老又重出江湖了？等会研究一下你的代码。

newkid

原帖由 grubbyoo 于 2009-9-4 13:07 发表
create view  tt0 as  
select   1 id,     2 amount from dual union all
select    2 ,     2 amount from dual union all
select    3 ,      3  amount from dual union all
.....

看了一下好像会死循环，我没敢试。
建视图的办法不好。你会产生一堆垃圾，而且每次循环不能利用前面的结果集。不如用临时表或嵌套表。
而且你的办法有可能一个ID出现多次，你没有仔细看需求吧？

郭清明

前辈，select power(2,419) from dual;在 oracle10g里面会报numeric overflow 错误，言外之意是不是这个算法只适合去查询数据量小于419条的表，一旦大于418条，数据库就会报错是吧

for i in res.first .. 2**res.last-1 loop 这个循环相当于要去计算 power(2,419)是吗

我那个需求是不是必须要用背包算法搞啊，我实际的数据量起码上万条，莫非无解？