kkkkkkkkkkkkkkkkkkkk

爱上狮子座女孩

N的数量级不大，只是研究下算法在数据库上的实现，谢谢你的解答

爱上狮子座女孩

真的很强大。。。还有一个经典算法，那就是贪心算法，贪心算法可以实现背包问题的最优解，但不能求出0/1背包问题的最优解，不知该如何求解用贪心算法实现背包问题：

背包问题：与0/1背包问题类似，所不同的是在选择物品 i 装入背包时，可以选择物品 i 的一部分，而不一定要全部装入背包。

实例：物品id=(1,2,3)  价值Vi=（60,100,120）  重量Wi=（10,20,30）  背包容量C=50   那么最优解的答案应该是取ID1+ID2+2/3 ID3=60+100+80=240

C语言算法实现如下：

1. 
   
2. #include <stdio.h>
   
3. #include <iostream.h>
   
4. 
   
5. #define MAXWEIGHT  50
   
6. #define  n 3
   
7. 
   
8. 
   
9. float pw[n]={0},x[n]={0};
   
10. int w[n]={0},p[n]={0};
    
11. 
    
12. void sort(int p[],int w[])
    
13. {
    
14.   int temp1,temp2;
    
15.   float temp;
    
16.   int i,j;
    
17.   for(i=0;i<n;i++)
    
18.   {
    
19.     pw[i]=float(p[i])/w[i];
    
20.   }
    
21. 
    
22. 
    
23.   for(i=0;i<n-1;i++)
    
24.   {
    
25.     for(j=i+1;j<n;j++)
    
26. {
    
27.   if(pw[i]<pw[j])
    
28.   {
    
29.    temp=pw[i],pw[i]=pw[j],pw[j]=temp;
    
30.    temp1=p[i],temp2=w[i];
    
31.    p[i]=p[j],w[i]=w[j];
    
32.    p[j]=temp1,w[j]=temp2;
    
33.   }
    
34. }
    
35. 
    
36.   }
    
37. 
    
38. 
    
39. }
    
40. 
    
41. 
    
42. 
    
43. 
    
44. void GreedyKnapsack(int p[],int w[])
    
45. {
    
46. int m=MAXWEIGHT,i;
    
47. for(i=0;i<n;i++)  x[i]=0.0;
    
48.     for(i=0;i<n;i++)
    
49. {
    
50.   if(w[i]>m)   break;
    
51.   x[i]=1.0;
    
52.   m=m-w[i];
    
53. }
    
54. if(i<n)   x[i]=float(m)/w[i];
    
55. 
    
56. 
    
57. 
    
58. 
    
59. }
    
60. 
    
61. 
    
62. 
    
63. 
    
64. void main()
    
65. {
    
66. int i;
    
67. printf("请输入每个物体的效益和重量:\n");
    
68. for(i=0;i<n;i++)
    
69. {
    
70.   cin>>p[i]>>w[i];
    
71. }
    
72.     for(i=0;i<n;i++)
    
73. {
    
74.   printf("原物体%d的效益和重量分别为%d,%d:\n",i+1,p[i],w[i]);
    
75. }
    
76.     sort(p,w);
    
77.     printf("\n\n\n按效益值非递增顺序排列物体:\n");
    
78.     for(i=0;i<n;i++)
    
79. {
    
80.   printf("物体%d的效益和重量分别为%d,%d  效益值为:%f\n",(i+1),p[i],w[i],pw[i]);
    
81.   
    
82. }
    
83. GreedyKnapsack(p,w);
    
84. printf("\n\n\n最优解为:\n");
    
85.     for(i=0;i<n;i++)
    
86. {
    
87. printf("第%d个物体要放%f:\n",i+1,x[i]);
    
88. }
    
89. 
    
90. 
    
91. }
    

复制代码

[ 本帖最后由 〇〇 于 2010-4-16 15:46 编辑 ]

〇〇

学习

newkid

#9有BUG, 因为每次循环都仅仅保留最近一次连接的结果，而最佳答案不一定在最外面的一层。改用外连接，如果连接不上但是总价值最高的答案也应该留下来。

DROP TYPE t_pack FORCE;

CREATE OR REPLACE TYPE t_pack AS OBJECT (id NUMBER, total_w NUMBER, total_v NUMBER, nodes VARCHAR2(1000),cnt NUMBER)
/

CREATE OR REPLACE TYPE tb_pack AS TABLE OF t_pack
/

DECLARE
  lv_limit NUMBER := 10;
  a_pack tb_pack;
  a_pack2 tb_pack;
BEGIN

  SELECT t_pack(id,weight,val,'(id='||id||' w='||weight||' v='||val||')',0)
   BULK COLLECT INTO a_pack
    FROM pack
   WHERE weight<=lv_limit;
  
  LOOP
    SELECT t_pack(id,total_w,total_v,nodes,COUNT(id) OVER())
      BULK COLLECT INTO a_pack2
      FROM (SELECT p.id
                  ,NVL(p.weight,0) + t.total_w AS total_w
                  ,NVL(p.val,0) + t.total_v AS total_v
                  ,nodes||(CASE WHEN p.id IS NULL THEN NULL ELSE ' (id='||p.id||' w='||p.weight||' v='||p.val||')' END) AS nodes
                  ,RANK() OVER(ORDER BY NVL(p.val,0) + t.total_v DESC) AS rnk
           FROM pack p RIGHT JOIN TABLE(a_pack) t
                ON t.id<p.id
                   AND p.weight + t.total_w<=lv_limit
           )
    WHERE id IS NOT NULL OR rnk=1;

    a_pack := a_pack2;
   
    IF a_pack.COUNT=0 OR a_pack(1).cnt=0 THEN
       EXIT;
    END IF;
  END LOOP;
  
  DBMS_OUTPUT.PUT_LINE(a_pack(1).nodes||' total_v='||a_pack(1).total_v);
END;
/

爱上狮子座女孩

newkid好敬业啊，万分感谢你的解答。。。

newkid

这篇文章说贪婪法不能保证最优解:
http://www.qnr.cn/pc/erji/C/ziliao/201004/425956.html

爱上狮子座女孩

贪婪算法本来就不能000求出0/1背包问题的最优解，但是可以求出背包问题的最优解，也就是当背包的物品可以取部分时，能得到最优解，以上有C语言用贪婪算法求背包问题的代码，但是不知道怎么“翻译”成PL/SQL，拜求。。。

〇〇

用index by table代替数组
效益*数量为key输出就是排好序的
然后翻译GreedyKnapsack

newkid

其实这个贪婪法啥也没做，就是排序一下而已。把它等价的PLSQL写出来，简直是笑死人：

DECLARE
   
   TYPE t_row IS TABLE OF pack%ROWTYPE INDEX BY BINARY_INTEGER;  
   lv_p t_row;     
   
   lv_limit NUMBER := 10;    ------ 重量限制
   m NUMBER := lv_limit;

BEGIN
   SELECT * BULK COLLECT INTO lv_p FROM pack ORDER BY val/weight;

   FOR i IN 1..lv_p.COUNT LOOP
       DBMS_OUTPUT.PUT('(id='||lv_p(i).id||' w='||lv_p(i).weight||' v='||lv_p(i).val||')-------');

       IF lv_p(i).weight>m THEN
          DBMS_OUTPUT.PUT_LINE(m/lv_p(i).weight);
          EXIT;
       ELSE
          DBMS_OUTPUT.PUT_LINE(1);
          m := m - lv_p(i).weight;
       END IF;
   END LOOP;
   
END;
/

网上有一些改良版本的，比如和什么“遗传算法”混合，你搜索一下就知道了。

我把自己#14的写法再改一下，用一个内存数组就够了：
DECLARE
  lv_limit NUMBER := 10;
  a_pack tb_pack;
BEGIN

  SELECT t_pack(id,weight,val,'(id='||id||' w='||weight||' v='||val||')',0)
   BULK COLLECT INTO a_pack
    FROM pack
   WHERE weight<=lv_limit;
  
  LOOP

    SELECT CAST(MULTISET(SELECT id,total_w,total_v,nodes,COUNT(id) OVER()
                           FROM (SELECT p.id
                                       ,NVL(p.weight,0) + t.total_w AS total_w
                                       ,NVL(p.val,0) + t.total_v AS total_v
                                       ,nodes||(CASE WHEN p.id IS NULL THEN NULL ELSE ' (id='||p.id||' w='||p.weight||' v='||p.val||')' END) AS nodes
                                       ,RANK() OVER(ORDER BY NVL(p.val,0) + t.total_v DESC) AS rnk
                                FROM pack p RIGHT JOIN TABLE(a_pack) t
                                     ON t.id<p.id
                                        AND p.weight + t.total_w<=lv_limit
                                )
                         WHERE id IS NOT NULL OR rnk=1
                         )
                 AS tb_pack
                 )
    INTO a_pack
    FROM DUAL;
   
    IF a_pack.COUNT=0 OR a_pack(1).cnt=0 THEN
       EXIT;
    END IF;
  END LOOP;
  
  DBMS_OUTPUT.PUT_LINE(a_pack(1).nodes||' total_v='||a_pack(1).total_v);
END;
/

[ 本帖最后由 newkid 于 2010-4-18 10:01 编辑 ]

〇〇

学习