幻想森林

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 3740|回复: 4

[通用编程] 再问个01背包问题(也是回溯法实现)

[复制链接]

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
发表于 2009-2-8 23:38:12 | 显示全部楼层 |阅读模式
图中给出3件物品(n), C是背包的容量,W,V就是1~n件物品的重量和价值。

相近的解题方法如下:
  1. #include<iostream>
  2. using namespace std;
  3. class Knap
  4. {
  5.     friend int Knapsack(int p[],int w[],int c,int n);
  6.     public:
  7.            void print()
  8.            {
  9.                for(int m=1;m<=n;++m)
  10.                    cout << bestx[m] << " ";
  11.                cout << endl;
  12.            }
  13.            
  14.     private:
  15.             int Bound(int i);
  16.             void Backtrack(int i);
  17.             int c; //背包容量
  18.             int n; //物品数
  19.             int *w;//物品重量数组
  20.             int *p;//物品价值数组
  21.             int cw;//当前重量
  22.             int cp;//当前价值
  23.             int bestp;//当前最优值
  24.             int *bestx;//当前最优解
  25.             int *x;//当前解
  26. };
  27. int Knap::Bound(int i)
  28. {
  29.     //计算上界
  30.     int cleft = c - cw;//剩余容量
  31.     int b = cp;
  32.    
  33.     //以物品单位重量价值递减序装入物品
  34.     while(i<=n && w[i]<=cleft)
  35.     {
  36.         cleft -= w[i];
  37.         b += p[i];
  38.         ++i;
  39.     }
  40.     //装满背包时
  41.     if(i<=n) b += p[i]/w[i]*cleft;
  42.     return b;
  43. }
  44. void Knap::Backtrack(int i)
  45. {
  46.     if(i>n)
  47.     {
  48.         if(bestp<cp)
  49.         {
  50.             for(int j=1;j<=n;++j)
  51.                 bestx[j] = x[j];
  52.             bestp = cp;
  53.         }
  54.         return;
  55.     }
  56.     if(cw+w[i]<=c) //搜索左子树
  57.     {
  58.         x[i] = 1;
  59.         cw += w[i];
  60.         cp += p[i];
  61.         Backtrack(i+1);
  62.         cw -= w[i];
  63.         cp -= p[i];
  64.     }
  65.     if(Bound(i+1)>bestp) //搜索右子树
  66.     {
  67.         x[i] = 0;
  68.         Backtrack(i+1);
  69.     }
  70. }
  71. class Object
  72. {
  73.     friend int Knapsack(int p[],int w[],int c,int n);
  74.     public:
  75.            int operator<=(Object a) const
  76.            {
  77.                return (d>=a.d);
  78.            }
  79.     private:
  80.             int ID;
  81.             float d;
  82. };
  83. int Knapsack(int p[],int w[],int c,int n)
  84. {
  85.     int W = 0;
  86.     int P = 0;
  87.     int i = 1;
  88.     Object *Q = new Object[n];
  89.    
  90.     for(i=1;i<=n;++i)
  91.     {
  92.         Q[i-1].ID = i;
  93.         Q[i-1].d = 1.0*p[i]/w[i];
  94.         P += p[i];
  95.         W += w[i];
  96.     }
  97.     if(W<=c)
  98.         return P; //装入所有物品
  99.     //依物品单位重量排序
  100.     float f;
  101.     for(i=0;i<n;++i)
  102.         for(int j=i;j<n;++j)
  103.         {
  104.            if(Q[i].d<Q[j].d)
  105.            {
  106.                f = Q[i].d;
  107.                Q[i].d = Q[j].d;
  108.                Q[j].d = f;
  109.            }
  110.         }
  111.         
  112.     Knap K;
  113.     K.p = new int[n+1];
  114.     K.w = new int[n+1];
  115.     K.x = new int[n+1];
  116.     K.bestx = new int[n+1];
  117.     K.x[0] = 0;
  118.     K.bestx[0] = 0;
  119.     for(i=1;i<=n;++i)
  120.     {
  121.         K.p[i] = p[Q[i-1].ID];
  122.         K.w[i] = w[Q[i-1].ID];
  123.     }
  124.     K.cp = 0;
  125.     K.cw = 0;
  126.     K.c = c;
  127.     K.n = n;
  128.     K.bestp = 0;
  129.     //回溯搜索
  130.     K.Backtrack(1);
  131.     K.print();
  132.     delete[] Q;
  133.     delete[] K.w;
  134.     delete[] K.p;
  135.     return K.bestp;
  136. }
  137. int main(void)
  138. {
  139.     int *p;
  140.     int *w;
  141.     int c=0;
  142.     int n=0;
  143.     int i=0;
  144.    
  145.     cout << "请输入物品个数n:" << endl;
  146.     cin >> n;
  147.     p = new int[n+1];
  148.     w = new int[n+1];
  149.     p[0] = 0;
  150.     w[0] = 0;
  151.    
  152.     cout << "请输入n个物品的价值:" << endl;
  153.     for(i=1;i<=n;++i)
  154.         cin >> p[i];
  155.    
  156.     cout << "请输入N个物品的重量:" << endl;
  157.     for(i=1;i<=n;++i)
  158.         cin >> w[i];
  159.         
  160.     cout << "请输入背包容量:" << endl;
  161.         cin >> c;
  162.         
  163.     cout << Knapsack(p,w,c,n) << endl;
  164.     system("PAUSE");
  165.     return 0;
  166. }
复制代码
还是比较多不懂的地方,像类里面的Bound方法最后那句://装满背包时
    if(i<=n) b += p/w*cleft;
第i物品的价值/第i物品的重量*背包剩余容量是什么意思?
在这个IF之前的循环不是已经把重量都得到了吗?

还有就是它到底是怎么分别左右子树的? 晕晕的

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复

使用道具 举报

20

主题

197

帖子

2641

积分

⑥精研

积分
2641
QQ
发表于 2009-2-9 10:57:48 | 显示全部楼层
这个算法的关键是把单个物品的价值最大的计算出来即p/w,然后放入到包中p/w*cleft,为确保有足够的空间,所以要IF一下,然后再放入包中,b += p/w*cleft;
签名要少于60,SO,i haven't upload my pic
回复 支持 反对

使用道具 举报

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
 楼主| 发表于 2009-2-9 12:01:51 | 显示全部楼层
还是不明白,单个物品的价值最大的计算出来? p不就是这物品的价值了吗?
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复 支持 反对

使用道具 举报

20

主题

197

帖子

2641

积分

⑥精研

积分
2641
QQ
发表于 2009-2-9 12:49:45 | 显示全部楼层
p是总体价值,不是单数价值
签名要少于60,SO,i haven't upload my pic
回复 支持 反对

使用道具 举报

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
 楼主| 发表于 2009-2-9 21:56:23 | 显示全部楼层
C++还只是学了点皮毛,这程序看得很吃力。于是把它转成C语言描述了。
  1. #include&lt;stdio.h&gt;
  2. #include&lt;stdlib.h&gt;
  3. int content;        //背包容量
  4. int n;              //物品数
  5. int *weight;        //存放n个物品重量的数组
  6. int *price;         //存放n个物品价值的数组
  7. int currentWeight;  //当前重量
  8. int currentPrice;   //当前价值
  9. int bestPrice;      //当前最优值
  10. int *bestAnswer;    //当前最优解
  11. int *cAnswer;       //当前解
  12. int Bound(int i) //检验子树是否能产生合适解的函数
  13. {
  14.     int cleft = content - currentWeight; //求背包剩余容量
  15.     int p = currentPrice; //当前背包所装物品价值
  16.    
  17.     while(i&lt;=n &amp;&amp; weight[i]&lt;=cleft)
  18.     {
  19.         cleft -= weight[i];
  20.         p += price[i];
  21.         ++i;
  22.     }
  23.     return p; //返回价值p
  24. }
  25. void Backtracking(int i)
  26. {
  27.     int j;
  28.     if(i&gt;n)
  29.     {
  30.         if(bestPrice&lt;currentPrice) //最优值小于当前价值则赋值
  31.         {
  32.             for(j=1;j&lt;=n;++j)
  33.                 bestAnswer[j] = cAnswer[j]; //取得树上路径
  34.             bestPrice = currentPrice;
  35.         }
  36.         return;
  37.     }
  38.     if(currentWeight+weight[i]&lt;=content)//当前重量+该物品重量 &lt;= 背包容量
  39.     {
  40.         //搜索左子树
  41.         cAnswer[i] = 1;
  42.         currentWeight += weight[i];
  43.         currentPrice += price[i];
  44.         Backtracking(i+1);
  45.         //完成上面的递归,返回到上一结点,准备递归右子树
  46.         currentWeight -= weight[i];
  47.         currentPrice -= price[i];
  48.     }
  49.     if(Bound(i+1)&gt;bestPrice) //搜索右子树,如返回值大于当前最优值,则执行
  50.     {
  51.          cAnswer[i] = 0;
  52.          Backtracking(i+1);
  53.     }
  54. }
  55. void Print()
  56. {
  57.     int i;
  58.    
  59.     printf(&quot;\\n\\nthe bestAnswer={&quot;);
  60.     for(i=1;i&lt;n;++i)
  61.         printf(&quot;%d,&quot;,bestAnswer[i]);
  62.     printf(&quot;%d}\\tthe bestPrice=%d\\n&quot;,bestAnswer[i],bestPrice);
  63. }
  64. void Destroy() //销毁分配空间
  65. {
  66.     free(price);
  67.     free(weight);
  68.     free(bestAnswer);
  69.     free(cAnswer);
  70. }
  71. int main(void)
  72. {
  73.     int i;
  74.     //输入物品数量
  75.     printf(&quot;please enter article amount:\\n&quot;);
  76.     scanf(&quot;%d&quot;,&amp;n);
  77.     //输入物品价格
  78.     printf(&quot;please enter all articles price:\\n&quot;);
  79.     if(!(price=(int*)malloc((n+1)*sizeof(int)))) exit(1);
  80.     for(i=1;i&lt;=n;++i)
  81.         scanf(&quot;%d&quot;,&amp;price[i]);
  82.     //输入物品重量
  83.     printf(&quot;please enter all articles weight:\\n&quot;);
  84.     if(!(weight=(int*)malloc((n+1)*sizeof(int)))) exit(1);
  85.     for(i=1;i&lt;=n;++i)
  86.         scanf(&quot;%d&quot;,&amp;weight[i]);
  87.     //输入背包容量   
  88.     printf(&quot;please enter knapsack&#39;s content:\\n&quot;);
  89.     scanf(&quot;%d&quot;,&amp;content);
  90.    
  91.     if(!(bestAnswer=(int*)malloc((n+1)*sizeof(int)))) exit(1);
  92.     if(!(cAnswer=(int*)malloc((n+1)*sizeof(int)))) exit(1);
  93.    
  94.     Backtracking(1);//回溯法搜索最优解
  95.     Print(); //打印结果
  96.   Destroy();
  97.    
  98.     system(&quot;PAUSE&quot;);
  99.     return 0;
  100. }
复制代码
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|幻想森林

GMT+8, 2024-11-1 07:39 , Processed in 0.035919 second(s), 22 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表