求一超难存储过程

qingyun

原帖由 zhangmei26 于 2009-8-28 11:07 发表

哇，真的好难啊

难个鸟啊，如果只是用最傻的那种回溯方法，不算难，也不难理解；难得的如何优化，提高运算效率；毕竟在运气不好的情况下，运算次数是个天文数字。

addm

原帖由 qingyun 于 2009-8-28 11:31 发表



难个鸟啊，如果只是用最傻的那种回溯方法，不算难，也不难理解；难得的如何优化，提高运算效率；毕竟在运气不好的情况下，运算次数是个天文数字。

newkid后面改进nyfor的办法已经很好了。
背包问题优化：把物体按从大往小的顺序放，尽早让包装满，尽早裁减分枝。


另外，请注意文明用语。

chen222246lei

declare
type test_t is table of t_money%rowtype index by binary_integer;
res test_t;
l_row binary_integer:=1;
sums number;
cal varchar2(1000);
seq varchar2(1000);
begin
for via in (select * from t_money) loop
  res(l_row):=via;
  l_row:=l_row+1;
end loop;
  --dbms_output.put_line(res.count);
  for i in res.first .. 2**res.last loop  -- <=> for i in 1..1024 loop
    sums:=0;
    seq:='';
    cal:='';
    for j in res.first .. res.count loop  -- <=> select j in 1 .. 10 loop
     if (bitand(i,2**j) <> 0) then
       sums:=sums+res(j).amount;
       cal:=cal||res(j).amount||'+';
       seq:=seq||j||',';
     end if;
    end loop;
    if (sums=10) then
     cal:=substr(cal,1,length(cal)-1);
     seq:=substr(seq,1,length(seq)-1);
     dbms_output.put_line('结果是:'||cal||'='||sums);
     dbms_output.put_line('序列是:'||seq);
     exit;
    end if;
  end loop;
end;

有问题如下：
1、对上面两个循环能玖举所有的情况表示怀疑，好像没什么有力论据
2、if (bitand(i,2**j) <> 0) then判断条件的依据是什么？个人感觉应该是内层循环j值不等于外层循环的i即可。

starfifi

同楼上
没想明白第二条 用位比较与判断j=i有什么区别

newkid

原帖由 chen222246lei 于 2009-8-28 16:56 发表 [url=http://www.itpub.net/redirect.php?goto=findpost&pid=14164837&ptid=1208469]
有问题如下：
1、对上面两个循环能玖举所有的情况表示怀疑，好像没什么有力论据
2、if (bitand(i,2**j)  0) then判断条件的依据是什么？个人感觉应该是内层循环j值不等于外层循环的i即可。

1. 假设总共有N行数据。每个数据可能被选中(1)或不被选中(0), 把它们看作一个二进制数的一位。总共有2^N种组合，这就是第一层循环。这个循环中每个数i代表一种组合
2. j是这个二进制数从右算起的第j位数, bitand(i,2**(j-1)) (注意这里的BUG我改了，应该是j-1) 这个结果如果不为0表示这种组合(i)里面必须包含第j位, 这个第二层循环就是找出组合i中所有的位，把它们对应的值加起来看看是否满足要求。

郭清明

原帖由 qingyun 于 2009-8-28 10:52 发表



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

算法不难理解，不过写起来还是挺有技巧的。
而且在比较糟糕的情况下，可能计算次数是个天文数字；电脑算上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! );降低了很多个数量级；

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

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

你的存储过程写的如何？有空的话，可不可以把你那个项目用的算法改写成pl/sql给大家分享一下，先谢谢你了。我是个oracle菜鸟，对于前面几位高手写的算法看得不是很明白（比如那个按位运算的算法），我希望能得到一个比较通俗易懂点的。

chen222246lei

原帖由 newkid 于 2009-8-28 21:28 发表


1. 假设总共有N行数据。每个数据可能被选中(1)或不被选中(0), 把它们看作一个二进制数的一位。总共有2^N种组合，这就是第一层循环。这个循环中每个数i代表一种组合
2. j是这个二进制数从右算起的第j位数, bitand(i,2**(j-1)) (注意这里的BUG我改了，应该是j-1) 这个结果如果不为0表示这种组合(i)里面必须包含第j位, 这个第二层循环就是找出组合i中所有的位，把它们对应的值加起来看看是否满足要求。

感谢newkid的解释，这个算法确实比较有新意，但有一点还不明白，假设总共有N行数据。每个数据可能被选中(1)或不被选中(0), 把它们看作一个二进制数的一位。应该总共有2^N－1种组合而不是2^N吧，那最外层的循环应该是for i in 1 .. 2**res.last -1 loop

newkid

原帖由 chen222246lei 于 2009-8-29 10:56 发表


感谢newkid的解释，这个算法确实比较有新意，但有一点还不明白，假设总共有N行数据。每个数据可能被选中(1)或不被选中(0), 把它们看作一个二进制数的一位。应该总共有2^N－1种组合而不是2^N吧，那最外层的循环应该是for i in 1 .. 2**res.last -1 loop

确实应该是2^N-1。如果不减1最后一轮循环是空转，但也不会错。

dhhb

for i in res.first .. 2**res.last loop  应该是for i in 1 .. 2**res.last-1 loop  吧?

郭清明

请教两个问题：
  1.如果实际当中的数据有上万条，而且没有一个组合能满足那个总金额，程序会死掉吗？

  2.在此题基础上再加一个需求：当查找不到满足此总金额的组合时，系统允许有容差，举例：容差为 1或者-1，总金额为10，当没有组合满足10的时候，那么9到11之间的组合也行，而且越接近10的组合越好，这样的需求在实现上有什么方法吗？即在上述pl/sql中可以做哪些修改，来满足此需求？

   谢谢