免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2121 | 回复: 0

[算法] 求助:队列分支法解0/1背包问题 [复制链接]

论坛徽章:
0
发表于 2017-04-01 15:40 |显示全部楼层
本帖最后由 proof 于 2017-04-01 15:51 编辑

教材上的程序,实验没有通过,请帮忙改一下,哪出错了?
----------------------------------------------------------

【例9】FIFO分支法解决0/1背包问题。
  数据结构设计:在回溯算法的辅助空间参数栈中,对高度为n的树,最多有n个数据,即依次存储树中一个分支各层结点的信息。而在分支法算法的辅助空间队中的结点,就无法识别结点间的层次等关系。所以队列中的数据要涵盖结点的所有信息。
  (1)i是结点所在层次,表示处理的是第i件物品。
  (2)变量flag存储物品的取舍情况,flag为1表示选取该物品,flag为0表示不选取该物品。
  (3)当前的利润cp和重量cw。
  (4)为了能方便输出最大利润的方案,用线性的数组队,每次扩展都记录活结点的父结点下标par。同时记录当前最大利润的最后一个物品的编号bestq。

----------------------------------------------------------
  1. #include <iostream>
  2. #include <iomanip>
  3. using namespace std;

  4. struct DEF_node {
  5.         int i,flag,par;
  6.         float cp,cw;
  7. };

  8. int w[]={0,1,2,3,4,5};                //重量
  9. int p[]={0,3,9,2,5,7};                //价值
  10. int n=5;                                        //物品个数
  11. int m=8;                                        //背包容量
  12. void algm(int,int);

  13. main() {
  14.         algm(n,m);
  15. }

  16. struct DEF_node enode,node,q[100];        //enode为当前扩展结点,node为 enode的子结点
  17. void algm(int n,int m) {
  18.         int f=0,e=0;                        //队首、队尾指针
  19.         int bestp=0,beste=0;
  20.         enode.cw=0;                                //初始化第1层
  21.         enode.cp=0;
  22.         enode.i=0;
  23.         enode.flag=0;
  24.         enode.par=0;
  25.         e++;
  26.         q[e]=enode;
  27.        
  28.         while (e!=0) {                                                //e=0子集空间树搜索完毕
  29.                 node.cw=enode.cw+w[enode.i+1];
  30.                 if (node.cw<=m) {                                //检查左孩子。可行的左孩子,取物品i
  31.                         node.cp=enode.cp+p[enode.i+1];
  32.                         if (node.cp>bestp) {
  33.                                 bestp=node.cp;
  34.                                 beste=e+1;
  35.                         }
  36.                         node.flag=1;
  37.                         node.par=f;
  38.                         node.i=enode.i+1;
  39.                         e++;
  40.                         q[e]=node;
  41.                 }
  42.                
  43.                 node.cw=enode.cw;                                //搜索右孩子,不取物品i
  44.                 node.cp=enode.cp;
  45.                 node.flag=0;
  46.                 node.par=f;
  47.                 node.i=enode.i+1;
  48.                 e++;
  49.                 q[e]=node;
  50.                
  51.                 f++;                                                        //取下一个E-结点
  52.                 enode=q[f];
  53.         }
  54.        
  55.        
  56.         for (int j=1; j>=n; j++) {                        //输出最大利润方案之一
  57.                 if (q[beste].flag==1)
  58.                         cout<<"choose"<<q[beste].i<<" ";
  59.                 beste=q[beste].par;
  60.         }
  61.         cout<<"Max="<<bestp<<endl;
  62. }
复制代码

感觉第32行很吊诡,因为循环体内e没有减小操作,没有满足循环终止条件e=0的可能。可是书上就是这么印的。是不是哪里有印刷错误?改了半天也没成功。
必须FIFO队列式分支法,不要“优先”队列式分支限界法。
求助一下。



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

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP