求一超难存储过程

郭清明

hierarchy.sys_sum_by_path  是什么东东啊？  我 用 oracle10g 跑你的代码的时候 报错，说 hierarchy.sys_sum_by_path 是无效的

newkid

原帖由 liuzhiqiangoracle 于 2009-8-26 14:56 发表
三楼的方法不错，学习了。4楼的优化中内层的循环上届为i不理解我觉得应该是10。

上界为i虽然没错但其实还不够好，第二层循环应该是：
WHILE res(j).pow <= i LOOP

因为再大的数已经超出i的最高位，与结果肯定是零。

newkid

原帖由 郭清明 于 2009-8-26 21:07 发表
hierarchy.sys_sum_by_path  是什么东东啊？  我 用 oracle10g 跑你的代码的时候 报错，说 hierarchy.sys_sum_by_path 是无效的

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);
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;
end;
/

newkid

原帖由 addm 于 2009-8-26 17:23 发表
dingjun123和newkid的办法本质上是穷举法，newkid的办法对筛选做了一些优化。
当包的数目增加的时候，穷举法的复杂度呈指数递增，为2^N次，N为包的个数。

背包问题的解法，为回溯法，用递归解决。nyfor的办法体现了递归的思想，但是没有在中途裁减分枝，只是在最后做了过滤。

nyfor的写法加上裁剪分支：

select path
  from (select rownum rn,
               hierarchy.sys_connect_by_path(level, id, ',') path,
               hierarchy.sys_sum_by_path(level, amount) amount
          from t_money
        connect by id > prior id
                AND hierarchy.sys_sum_by_path(level, amount)<=10      --- 中途裁剪
        )
where amount = 10;

如果要在求出第一个解就停止，只要在hierarchy包加上标记变量，并在CONNECT BY中判断即可。
不过这个方法依赖于函数的调用顺序，我曾经在ASKTOM上问过，TOM对此持否定态度。

郭清明

index by binary_integer 是 什么 意思 啊？  

在 oracle10g 里面有没有这个类型？我把代码copy到pl/sql里面运行的时候报错了，
另外for i in res.first .. 2**res.last-1 loop    其中的“**”是什么意思， oracle10G 支持这种表达式吗？

你的QQ号码多少，可以认识一下吗，谢谢。

newkid

报什么错？我在10G的SQLPLUS下运行没问题。
index by binary_integer是定义数组(Associative Arrays)的语法, 表示以整数为下标。
**是PL/SQL的求幂运算操作符。
我没有QQ号。

郭清明

原帖由 newkid 于 2009-8-27 03:25 发表
报什么错？我在10G的SQLPLUS下运行没问题。
index by binary_integer是定义数组(Associative Arrays)的语法, 表示以整数为下标。
**是PL/SQL的求幂运算操作符。
我没有QQ号。

create or replace procedure P_test(sum_num in number)
as
       v_str      varchar2(200):=',';
       v_id       number;
       v_count    number;
       v_tmp      number :=0;
       v_money    number :=0;
       v_length   number:=0;
       v_count1   number;
begin
      
       select count(0) into v_count1 from t_money;
       loop
           select count(0) into v_count from t_money where not instr(v_str,','||id||',')>0 and amount <= sum_num-v_money;
           if v_count = 0  then
           if v_length=v_count1 then
            dbms_output.put_line('error:the input-value is too large');
            return;
           end if;
             v_str:=',';
            
             v_money:=0;
            
              -- or restart
           end if;

           select id,amount into v_id,v_tmp from
                  (select id,amount from t_money where not instr(v_str,','||id||',')>0 and amount <= sum_num-v_money order by dbms_random.value)
                where rownum <2;
           v_money := v_money + v_tmp;
           v_str := v_str || v_id ||',';
           v_length:=v_length+1;
           exit when v_money =sum_num;

       end loop;
      
       dbms_output.put_line('id组合: '||substr(v_str,2));      
      
end p_test;

这个算法如何？

newkid

这个算法不行，根本没有回溯功能只是碰运气，可能永远找不到答案。

qingyun

靠，这个问题跟我以前问的帖子一摸一样。

http://www.itpub.net/viewthread. ... 12353197pid12353197

就是解决买东西不找零这类问题。我已经在项目中使用了。呵呵。

那天我抽空把我项目中的代码修改一下，按照楼主的命题贴出来，不过基本和newKid兄的差不多。

当时，我是参考我delphi的代码做的：

==============================================


算法我已经比较完整的实现了。
不过是参考网上的delphi的代码,转换成pl/sql应该也不是难事；


我做了个demo演示程序，运行效率非常高；

大家可以看看效果：
程序下载地址：
http://www.daizhicun.com/dmx/dai/OutMatch.rar

截图：








主要代码：
http://www.daizhicun.com/dmx/dai/OutMatch.txt

[ 本帖最后由 qingyun 于 2009-8-28 11:40 编辑 ]

qingyun

原帖由 newkid 于 2009-8-28 01:16 发表
这个算法不行，根本没有回溯功能只是碰运气，可能永远找不到答案。

说的太对了，回溯是核心， 其实该算法类似蚂蚁走迷宫，走一段，发现不行，再退后到前一段，走前一段的另外一个分支再走，直到找到一条正确的路线。

算法不难理解，不过写起来还是挺有技巧的。
而且在比较糟糕的情况下，可能计算次数是个天文数字；电脑算上1年也搞不定；

举个简单的例子，比如需要1万元，现在有的钞票共500张，各种面额均有；
要找出一种正好等于1万元的组合，理论上共有power(2,500)的组合，这个组合多大呢？
用  select power(2,500) from dual 执行以下 ，结果是： 执行失败:ORA-01426: numeric overflow
看来number已经没法表示了；

如果运气不好的话，算到比较靠后，才能得到第一个组合，那么就运算不错来了；

当时，我在客户那里也遇到这个问题：我做的项目是立体库的库存管理，当要出库的时候，比如出1万件，库存很多货位上都有，有的100件，有的50件，数量不等，但是每个货位的商品要么全部出库，要么不出库，不允许出一半留一半；所以我也是用这个回溯的算法去找；
可惜有的时候运气不好，找个很久都不能出来；我在运算前，把所有的相关库存都锁住了，所以这个运算时间要非常快才行；结果没有办法，我限定了次数，运算最多100万次，多了就不算了，让它人工去选库存；


  其实，我研究的不够深入，算法其实还可以在优化，就拿上面的1万元来说。

这500张面值的钞票了，肯定有重复的，比如100元50张，50元75张。20元47张.......

  把重复的归类，然后在设计算法，可以大大减少运算次数，
这就类似排列组合中：假如有10个不同颜色的小球，其排列共有10!种；
                    但是如果其中3个红色，3个黄色，4个蓝色，那么排列就是10!/(3!*3!*4! );降低了很多个数量级；

当然这个算法，就不仅仅是回溯那么简单了，要考虑的东西多了；是多个算法的集合体；而且不要做那种一个个的历遍；

  不过，我们毕竟不是数学家，对算法不敏感 ，很难研究并实现那些生猛的算法。  我一直觉得的生活中很多现象，都可以建立算法模型，可惜很多时候，都要用到很多高深的数学理论；

[ 本帖最后由 qingyun 于 2009-8-28 11:28 编辑 ]