当前位置:首页 >> IT/计算机 >>

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


华北水利水电学院
2009 ~2010 班级: 一、 实验题目: 200915326

数据结构与算法分析 实验报告
学期 2009 级 200915326 计算机 专业 学号: 姓名: 郜莉洁

学年 第 1

分别用回溯法和分支限界法求解 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 <iostream.h> #define MaxSize 100 int limitw; int maxwv=0; int int int int maxw; n; option[MaxSize]; 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<n;j++) option[j]=op[j]; } }
第 页 共 页

else { op[i]=1; //选取第 I 个物品 Knap(i+1,tw+a[i].weight, tv+a[i].value); op[i]=0; //不选取第 I 个物品,回溯 Knap(i+1,tw,tv); } } int main(int argc, char* argv[]) { int j; n=3; //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<<"最佳装填方案是:"<<endl; for(j=0;j<n;j++) if(option[j]==1) cout<<"第"<<j+1<<"种物品"<<endl; cout<<"总重量="<<maxw<<",总价值="<<maxwv<<endl; return 0; }

//限制重量不超过 30

回溯法测试结果: 测试数据:物品一:重量:16,价格:45; 物品二:重量:15,价格:25; 物品三:重量:15,价格:25;









B:分支限界法: #include <stdio.h> #include<malloc.h> #define MaxSize 100 typedef { float float weight; value; struct QNode //最多结点数

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)) 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++)
第 页 共 页

// 左儿子结点进队列

//右儿子总是可行; // 取下一扩展结点

break; // 同层结点尾部标志 // 取下一扩展结点

//更新当前扩展结点的值

//构造最优解

{ 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
回溯法和分支限界法解决0-1背包题_计算机软件及应用_IT/计算机_专业资料。用...方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。...
分别用回溯法和分支限界法求解0-1背包问题.doc
分别用回溯法和分支限界法求解0-1背包问题_IT/计算机_专业资料。分别用回溯法和分支限界法求解0-1背包问题华北水利水电学院 2009 ~2010 班级: 一、 实验题目: ...
回溯法和分支限界法解决0-1背包题(精).doc
0-1 背包问题 计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一 个(...
回溯法和分支限界法解决0-1背包题要点.doc
回溯法和分支限界法解决0-1背包题要点_其它_职业教育_教育专区。0-1 背包问题计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题 - 一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/1 背包问题。 注: 0/1 背包...
用回溯法和队列式分支限界算法求解0-1背包问题.doc
用回溯法和队列式分支限界算法求解0-1背包问题 - 华北水利水电学院 2009
回溯法、分支限界法解0-1背包问题(计算机算法设计与分....doc
回溯法分支限界法解0-1背包问题(计算机算法设计与分析实验报告) - 报告中附
回溯法求0-1背包问题.doc
回溯法求0-1背包问题 - 《算法设计分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量...
0-1背包问题(分支限界法).doc
分支限界法01 背包问题 12 软工一、 问题描述 0-1 背包问题: 给定 n ...分别用回溯法和分支限界... 8页 2下载券 利用分枝界限法求解0-1背... ...
算法设计与分析复习题目及答案.doc
不可以使用分治法求解的是(0/1 背包问题 )。 动态规划 下列不是动态规划算法...回溯法和分支限界法,其中不需要排 序的是 动态规划 ,需要排序的是 回溯法 ,...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题 - 一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/1 背包问题。 注:0/1 背包...
算法分析复习题目及答案.doc
代码短 8、以下不可以使用分治法求解的是( D )。...回溯法 42.0-1 背包问题的回溯算法所需的计算时间...回溯法和分支限界法,其中不需要排序的是 动 态规划...
算法分析复习题目及答案.doc
代码短 8、以下不可以使用分治法求解的是(D )。 ...回溯法 42.0-1 背包问题的回溯算法所需的计算时间...回溯法和分支限界法,其中不需要排 序的是 动态规划...
算法分析与设计复习题及参考答案.doc
6.简要分析分支限界法与回溯法的异同。 7.简述算法复杂性的概念,算法复杂性...4.根据分枝限界算法基本过程,求解 0-1 背包问题。 已知 n=3,M=20,(w1,w2...
优先队列式分支限界法求解0-1背包问题_图文.doc
优先队列式分支限界法求解0-1背包问题 - 算法分析设计实验报告 第 7 次实
回溯法在0_1背包问题中的应用.pdf
i=1 1 回溯法的基本思想回溯法通过系统地搜索一个问题的解空间 来得到 问题 的 3 3.1 回溯法求解 0-1背包问题定义问题的解空间 根据上述 0-1 背包问题的...
分支限界法解01背包问题.doc
分支限界法解 01 背包问题学院:网研院 、 分支限界法原理 姓名:XXX 学号:2013XXXXXX 分支限界法类似于回溯法, 也是在问题的解空间上搜索问题解的算法。 ...
算法分析复习题(含答案).doc
(D)回溯法 4、使用分治法求解不需要满足的条件是(...0/1 背包问题 8、实现循环赛日程表利用的算法是(...(A)分支界限算法 (B)动态规划算法 (C)贪心算法 ...
算法分析复习题目及答案.doc
D、回溯法 15.分支限界法解最大团问题时,活结点...(B ) A NP 问题都是不可能解决的问题 B P 类...回溯法 42.0-1 背包问题回溯算法所需的计算时间...
1、算法分析复习题目及答案.doc
分支限界法解最大团问题时,活结点表的组织形式是(...( A、贪心法 B、动态规划法 42.0-1 背包问题的...5 用回溯法搜索子集树的算法为: void backtrack ...
更多相关标签: