本帖最后由 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。
----------------------------------------------------------
- #include <iostream>
- #include <iomanip>
- using namespace std;
- struct DEF_node {
- int i,flag,par;
- float cp,cw;
- };
- int w[]={0,1,2,3,4,5}; //重量
- int p[]={0,3,9,2,5,7}; //价值
- int n=5; //物品个数
- int m=8; //背包容量
- void algm(int,int);
-
- main() {
- algm(n,m);
- }
- struct DEF_node enode,node,q[100]; //enode为当前扩展结点,node为 enode的子结点
- void algm(int n,int m) {
- int f=0,e=0; //队首、队尾指针
- int bestp=0,beste=0;
- enode.cw=0; //初始化第1层
- enode.cp=0;
- enode.i=0;
- enode.flag=0;
- enode.par=0;
- e++;
- q[e]=enode;
-
- while (e!=0) { //e=0子集空间树搜索完毕
- node.cw=enode.cw+w[enode.i+1];
- if (node.cw<=m) { //检查左孩子。可行的左孩子,取物品i
- node.cp=enode.cp+p[enode.i+1];
- if (node.cp>bestp) {
- bestp=node.cp;
- beste=e+1;
- }
- node.flag=1;
- node.par=f;
- node.i=enode.i+1;
- e++;
- q[e]=node;
- }
-
- node.cw=enode.cw; //搜索右孩子,不取物品i
- node.cp=enode.cp;
- node.flag=0;
- node.par=f;
- node.i=enode.i+1;
- e++;
- q[e]=node;
-
- f++; //取下一个E-结点
- enode=q[f];
- }
-
-
- for (int j=1; j>=n; j++) { //输出最大利润方案之一
- if (q[beste].flag==1)
- cout<<"choose"<<q[beste].i<<" ";
- beste=q[beste].par;
- }
- cout<<"Max="<<bestp<<endl;
- }
复制代码
感觉第32行很吊诡,因为循环体内e没有减小操作,没有满足循环终止条件e=0的可能。可是书上就是这么印的。是不是哪里有印刷错误?改了半天也没成功。
必须FIFO队列式分支法,不要“优先”队列式分支限界法。
求助一下。
|