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

回溯法解0-1背包问题实验报告


实验 4
一 、实验要求

回溯法解 0-1 背包问题

1.要求用回溯法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。

实验仪器和软件 软件平台 二 、实验仪器和软件平台
仪器 :带 usb 接口微机 软件平台:WIN-XP + VC++6.0

三 、实验源码
#include "stdafx.h" #include<iostream> #include<cstdio> #include<conio.h> #include<iomanip> using namespace std; template<class ty> class Knap { public: friend void Init(); friend void Knapsack(); friend void Backtrack(int i); friend float Bound(int i); bool operator<(Knap<ty> a)const { if(fl<a.fl) return true; else return false; } private: ty w; //重量 ty v; //价值 float fl; //单位重量的价值 v/w int kk; //记录第几个物品 int flag; //记录是否放入包中 }; template<class ty> void Sort(Knap<ty> *li,int n) {

int i,j,k; Knap<ty> minl; for(i=1;i<n;i++) { minl=li[0]; k=0; for(j=1;j<=n-i;j++) { if(minl<li[j]) { minl=li[j]; swap(li[j],li[k]); } } }

k=j;

} namespace jie //命名空间 { int c=0,n=0; int *x=NULL; Knap<int> *bag=NULL; int cp=0,cw=0; int bestp=0; } using namespace jie; void Init() { int i=0; cout<<endl; cout<<"请输入物品数量 n = "; cin>>n; cout<<endl; cout<<"请输入背包容量 C = "; cin>>c; cout<<endl; bag=new Knap<int> [n]; x=new int[n]; cout<<"请依次输入"<<n<<"个物品的重量 W:"<<endl; for(i=0;i<n;i++) cin>>bag[i].w; cout<<endl; cout<<"请依次输入"<<n<<"个物品的价值 P:"<<endl; for(i=0;i<n;i++) cin>>bag[i].v; for(i=0;i<n;i++) { bag[i].flag=0; bag[i].kk=i; bag[i].fl=1.0*bag[i].v/bag[i].w; } }

void Backtrack(int i) { if(i>=n) //到达叶节点 { bestp=cp; //更新最优价值 return; } if(cw+bag[i].w<=c) //进入左子树 { bag[i].flag=1; cw+=bag[i].w; cp+=bag[i].v; Backtrack(i+1); cw-=bag[i].w; cp-=bag[i].v; } if(Bound(i+1)>bestp)//进入右子树 { bag[i].flag=0; Backtrack(i+1); } } //计算当前节点处的上界 float Bound(int i) { int cleft = c-cw; //剩余容量 float b = cp; while (i<n&&bag[i].w<=cleft) { //以物品单位重量价值递减序装入 cleft-=bag[i].w ; b+=bag[i].v; i++; } //装满背包 if (i<n) b+=1.0*bag[i].v/bag[i].w * cleft; return b; } void Knapsack() //计算最优解和变量值 { int L(0); //用 L 累计价值,初始价值设置为 0 for(int k=0;k<n;k++) { x[bag[k].kk]=bag[k].flag; //x=0 表示未放入背包,x=1 表示放入背包 L+=bag[k].flag*bag[k].v; //价值累加 } cout<<endl; cout<<"当前最优价值为:"<<L<<endl; cout<<"变量值 x = ";

for(int i=1;i<=n;i++) { cout<<x[i-1]; } delete []bag; bag=NULL; delete []x; x=NULL; cout<<endl; getch(); } int main() { cout<<endl; cout<<"|**********回溯法解 0-1 背包问题**********|"<<endl; Init(); Backtrack(0); Knapsack(); return 0; }

四 、运行结果

实验小结 五 、实验小结
通过该实验,我充分了解了回溯法与分支界限法的区别。回溯法在问题的解 空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树 的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该 结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深 度优先策略搜索。


相关文章:
回溯法求0-1背包问题
回溯法求0-1背包问题 - 《算法设计与分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量...
回溯算法解决0-1背包问题(DOC)
回溯算法解决0-1背包问题(DOC) - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称...
回溯法实验(0-1背包问题)
回溯法实验(0-1背包问题) - 算法分析与设计实验报告 第五 次附加实验 姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法实验(0-1 背包...
用回溯法解决0-1背包问题
标签: 回溯法| 背包| 用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决0-1背包问题 #include&lt;stdio.h&gt; int c; //背包容量 ...
回溯法、分支限界法解0-1背包问题(计算机算法设计...
回溯法、分支限界法解0-1背包问题(计算机算法设计与分析实验报告) - 报告中附有可直接运行代码和实验结果截图(西大学子)。 编程语言:java 开发工具:eclipse 3.4...
0-1背包问题的解决(回溯法)
回溯法| 背包| 0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题。 前面...
回溯法-0-1背包问题
回溯法-0-1背包问题 - 1、 问题描述 一、0-1 背包问题 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,如何选择才能使 得物品的总价格最高...
回溯法和分支限界法解决0-1背包题(精)
0-1 背包问题 计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一 个(...
0-1背包问题(回溯法)
0-1背包问题(回溯法) - 0-1 背包问题(回溯法) 实验报告 姓 名: 学 号: 指导老师: 一.算法设计名称: 0-1 背包问题(回溯法) 二.实验内容 问题描述: ...
回溯法解决符号三角形与0-1背包问题
宁夏师范学院数学与计算机科学学院 《算法分析与设计》实验报告实验序号:9 学号姓 实验项目名称:回溯法解决符号三角形与 0-1 背包问题 名 专业、班时间 2014.06....
更多相关标签: