分别用回溯法和分支限界法求解0-1背包问题

华北水利水电学院 数据结构与算法分析 实验报告2009 2010 学年 第 1 学期 2009 级 计算机 专业班级： 学号： 姓名： 郜莉洁 一、 实验题目：分别用回溯法和分支限界法求解0-1背包问题二、 实验内容：0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。三、 程序源代码：A:回溯法：/ bag1.cpp : Defines the entry point for the console application./#include stdafx.h#include #define MaxSize 100 /最多物品数int limitw; /限制的总重量int maxwv=0; /存放最优解的总价值int maxw;int n; /实际物品数int optionMaxSize; / 存放最终解int opMaxSize; /存放临时解struct int weight; int value; aMaxSize; /存放物品数组void Knap( int i, int tw, int tv) /考虑第i个物品int j; if(i=n) /找到一个叶子结点 if (twmaxwv) /找到一个满足条件地更优解，保存它 maxwv=tv; maxw=tw; for(j=0;jn;j+) optionj=opj; else opi=1; /选取第I个物品 Knap(i+1,tw+ai.weight, tv+ai.value); opi=0; /不选取第I个物品，回溯 Knap(i+1,tw,tv); int main(int argc, char* argv)int j; n=3; /3物品 a0.weight=16;a0.value=45; a1.weight=15;a1.value=25; a2.weight=15;a2.value=25; /a3.weight=1;a3.value=1; limitw=30; /限制重量不超过30 Knap(0,0,0); cout最佳装填方案是：endl; for(j=0;jn;j+) if(optionj=1) cout第j+1种物品endl;cout总重量maxw,总价值maxwvendl;return 0;回溯法测试结果：测试数据：物品一：重量：16，价格：45；物品二：重量：15，价格：25；物品三：重量：15，价格：25；B：分支限界法： #include #include#define MaxSize 100 /最多结点数typedef struct QNode float weight; float value; intceng; struct QNode *parent; bool leftChild;QNode,*qnode; /存放每个结点typedef struct qnode QMaxSize; int front,rear;SqQueue; /存放结点的队列SqQueue sq;float bestv=0; /最优解int n=0; /实际物品数float wMaxSize; /物品的重量float vMaxSize;/物品的价值int bestxMaxSize; / 存放最优解qnode bestE;void InitQueue(SqQueue &sq ) /队列初始化sq.front=1;sq.rear=1;bool QueueEmpty(SqQueue sq) /队列是否为空if(sq.front=sq.rear)return true;else return false;void EnQueue(SqQueue &sq,qnode b)/入队if(sq.front=(sq.rear+1)%MaxSize)printf(队列已满!);return ;sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;qnode DeQueue(SqQueue &sq)/出队qnode e;if(sq.front=sq.rear)printf(队列已空!);return 0;e=sq.Qsq.front;sq.front=(sq.front+1)%MaxSize;return e;void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)qnode b;if (i=n) /可行叶子结点if (vt=bestv)bestE=parent;bestxn=(leftchild)?1:0;return;b=(qnode)malloc(sizeof(QNode); /非叶子结点b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent; b-leftChild=leftchild; EnQueue(sq,b); void maxLoading(float w,float v,int c) float wt=0;float vt=0;int i=1; /当前的扩展结点所在的层float ew=0; /扩展节点所相应的当前载重量float ev=0; /扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t); /空标志进队列while (!QueueEmpty(sq) wt=ew+wi; vt=ev+vi;if (wt bestv) bestv=vt;EnQueue1(wt,vt,i,e,true); / 左儿子结点进队列 EnQueue1(ew,ev,i,e,false); /右儿子总是可行；e=DeQueue(sq); / 取下一扩展结点if (e = NULL)if (QueueEmpty(sq) break;EnQueue(sq,NULL); / 同层结点尾部标志e=DeQueue(sq); / 取下一扩展结点i+;ew=e-weight; /更新当前扩展结点的值ev=e-value;printf(最优取法为：n);for( int j=n-1;j0;j-) /构造最优解bestxj=(bestE-leftChild?1:0);bestE=bestE-parent;for(int k=1;k=n;k+)if(bestxk=1)printf(n物品%d:重量：%.1f，价值：%.1fn,k,wk,vk);printf(n);printf(最优价值为：%.1fnn,bestv); void main()int c;float ewvMaxSize;printf( / 0-1背包问题分枝限界法 /nn);printf(请输入物品的数量：n);scanf(%d,&n);printf(请输入背包的最大承重量：n);scanf(%d,&c);printf(n请输入物品的重量和单位重量价值:nn);for(int i=1;i=n;i+)printf(物品%d:,i);scanf(%f%f,&wi,&ewvi);vi=wi*ewvi;printf(n);maxLoading(w, v, c); 分支限界法测试结果：五、小结（包括收获、心得体会、存在的问题及解决