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

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.08M 资料格式：doc 举报版权申诉

第1页 / 共8页

zylyk-2371633-分别用回溯法和分支限界法求解0-1背包问题.doc.pdf-第2页.png

第2页 / 共8页

zylyk-2371633-分别用回溯法和分支限界法求解0-1背包问题.doc.pdf-第3页.png

第3页 / 共8页

zylyk-2371633-分别用回溯法和分支限界法求解0-1背包问题.doc.pdf-第4页.png

第4页 / 共8页

zylyk-2371633-分别用回溯法和分支限界法求解0-1背包问题.doc.pdf-第5页.png

第5页 / 共8页

zylyk-2371633-分别用回溯法和分支限界法求解0-1背包问题.doc.pdf-第6页.png

第6页 / 共8页

zylyk-2371633-分别用回溯法和分支限界法求解0-1背包问题.doc.pdf-第7页.png

第7页 / 共8页

zylyk-2371633-分别用回溯法和分支限界法求解0-1背包问题.doc.pdf-第8页.png

第8页 / 共8页

文本预览

华北水利水电学院数据结构与算法分析实验报告 2009 ～2010 学年第 1 学期 2009 级计算机专业班级： 200915326 学号： 200915326 姓名：郜莉洁一、实验题目：分别用回溯法和分支限界法求解 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 option[MaxSize]; int op[MaxSize]; struct { int weight; int value; }a[MaxSize]; //最多物品数 //限制的总重量 //存放最优解的总价值 //实际物品数 // 存放最终解 //存放临时解 void Knap( int i, int tw, int tv) { int j; if(i>=n) { //存放物品数组 //考虑第 i 个物品 //找到一个叶子结点 if (tw<=limitw && tv>maxwv) { //找到一个满足条件地更优解，保存它 maxwv=tv; maxw=tw; for(j=0;j

op[i]=1; Knap(i+1,tw+a[i].weight, tv+a[i].value); op[i]=0; Knap(i+1,tw,tv); //选取第 I 个物品 //不选取第 I 个物品，回溯 else { } } int main(int argc, char* argv[]) { //3 物品 int j; n=3; a[0].weight=16;a[0].value=45; a[1].weight=15;a[1].value=25; a[2].weight=15;a[2].value=25; //a[3].weight=1;a[3].value=1; limitw=30; Knap(0,0,0); cout<<"最佳装填方案是："<

B：分支限界法： #include #include #define MaxSize 100 //最多结点数 typedef struct QNode { float weight; float value; int ceng; struct QNode *parent; bool leftChild; }QNode,*qnode; typedef struct { qnode Q[MaxSize]; int front,rear; //存放每个结点 }SqQueue; //存放结点的队列 SqQueue sq; float bestv=0; //最优解 int n=0; float w[MaxSize]; float v[MaxSize]; //实际物品数 //物品的重量 //物品的价值 int bestx[MaxSize]; // 存放最优解 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.Q[sq.rear]=b; sq.rear=(sq.rear+1)%MaxSize; qnode DeQueue(SqQueue &sq)//出队 { } qnode e; if(sq.front==sq.rear) { } printf("队列已空!"); return 0; e=sq.Q[sq.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; bestx[n]=(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+w[i]; vt=ev+v[i]; if (wt <= c) { } if(vt>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;j>0;j--) //构造最优解 { } bestx[j]=(bestE->leftChild?1:0); bestE=bestE->parent; for(int k=1;k<=n;k++) 第页共页

{ } if(bestx[k]==1) printf("\n 物品%d:重量：%.1f，价值：%.1f\n",k,w[k],v[k]); printf("\n"); printf("最优价值为：%.1f\n\n",bestv); } void main() { int c; float ewv[MaxSize]; printf(" //////////////////// 0-1 背包问题分枝限界法 /////////////////////\n\n"); printf("请输入物品的数量：\n"); scanf("%d",&n); printf("请输入背包的最大承重量：\n"); scanf("%d",&c); printf("\n 请输入物品的重量和单位重量价值:\n\n"); for(int i=1;i<=n;i++) { } printf("物品%d:",i); scanf("%f%f",&w[i],&ewv[i]); v[i]=w[i]*ewv[i]; printf("\n"); maxLoading(w, v, c); } 分支限界法测试结果：第页共页

五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距，不得少于 100 字。 1 通过这次试验是我对数据结构有了进一步的了解，可以通过算法解决实际问题（背包问题）。 2 在用分支限界法实现问题时遇到了有关队列的问题，通过上网搜索，问老师得以解决。 3 在老师有计划的指导安排下，我的编程能力突飞猛进，在此，对老师深表感谢！！第页共页

分享到：

赞收藏

资料库

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

相关推荐

课程资源

热门标签

最新资料