kkkkkkkkkkkkkkkkkkkk

爱上狮子座女孩

学习

爱上狮子座女孩

newkid关于贪婪算法的代码里有个小小的失误， 在SELECT * BULK COLLECT INTO lv_p FROM pack ORDER BY val/weight这个语句里，应该从大到小排序，所以应该最后加个 DESC ，这样在后面的贪婪过程中才能得到最优解

newkid

原帖由 爱上狮子座女孩 于 2010-4-20 17:02 发表
newkid关于贪婪算法的代码里有个小小的失误， 在SELECT * BULK COLLECT INTO lv_p FROM pack ORDER BY val/weight这个语句里，应该从大到小排序，所以应该最后加个 DESC ，这样在后面的贪婪过程中才能得到最优解

确实是这样，应该是“价值密度”大的优先。
其实那个内存数组都可以去掉，直接用个游标就行了：

DECLARE
   
   lv_limit NUMBER := 10;    ------ 重量限制
   m NUMBER := lv_limit;

BEGIN
   FOR lv_rec IN (SELECT * FROM pack ORDER BY val/weight DESC) LOOP
       DBMS_OUTPUT.PUT('(id='||lv_rec.id||' w='||lv_rec.weight||' v='||lv_rec.val||')-------');

       IF lv_rec.weight>m THEN
          DBMS_OUTPUT.PUT_LINE(m/lv_rec.weight);
          EXIT;
       ELSE
          DBMS_OUTPUT.PUT_LINE(1);
          m := m - lv_rec.weight;
          IF m=0 THEN
             EXIT;
          END IF;
       END IF;

   END LOOP;
   
END;
/

newkid

穷尽法：利用11GR2的递归WITH子查询：

WITH t (id , total_w , total_v , nodes ) AS (
  SELECT id,weight,val,'(id='||id||' w='||weight||' v='||val||')'
    FROM pack
   WHERE weight<=10    --- 假设限制为10
UNION ALL
SELECT p.id,p.weight + t.total_w,p.val + t.total_v,nodes||' (id='||p.id||' w='||p.weight||' v='||p.val||')'
  FROM pack p,t t
WHERE t.id<p.id
       AND p.weight + t.total_w<=10   --- 假设限制为10
  )
SELECT nodes,total_v
  FROM (SELECT * FROM t ORDER BY total_v DESC)
WHERE ROWNUM=1;

(id=1 w=2 v=6) (id=2 w=2 v=3) (id=5 w=4 v=6)    15

比起#14的PLSQL版本，这个SQL不能够及时甩掉明显不是最优的解。

yyp2009

newkid师傅厉害！

srzyhead

为啥标题和1楼都变成k*了?

cow977

不知道.

killkill_shadow

怎么个情况，内容都变成了 kkkkkk
楼下dingjun和newkid都非常卖力地回答，很诡异啊。

lastwinner

楼主不知道珍惜他人的回答，拿了答案就撤人，这行为很不好。
锁帖。