当前位置:首页 >> 幼儿读物 >>

回溯算法解决0-1背包问题(DOC)


《算法分析与设计》

实验报告

2015-2016 年第 2 学期

实验班级: 学生姓名: 学 号:

指导老师:

信息工程学院

实验项目名称:回溯算法解决 0-1 背包问题 实验日期:2016 年 5 月 18 日 一、实验类型: 二、实验目的
掌握 0—1 背包问题的回溯算法
√ 验证性 □

□设计性

三、实验内容及要求
给定 n 种物品和一背包。物品 i 的重量是 wi,其价值为 vi,背包的容量为 C。问应 如何选择装入背包的物品,使得装入背包中物品的总价值最大?

四、实验步骤
#include<iostream> using namespace std; class Knap { friend int Knapsack(int p[],int w[],int c,int n ); public: void print() { for(int m=1;m<=n;m++) { } cout<<endl; }; private: int Bound(int i); void Backtrack(int i); int c;//背包容量 int n; //物品数 int *w;//物品重量数组 int *p;//物品价值数组 cout<<bestx[m]<<" ";

int cw;//当前重量 int cp;//当前价值 int bestp;//当前最优值 int *bestx;//当前最优解 int *x;//当前解 }; int Knap::Bound(int i) { //计算上界 int cleft=c-cw;//剩余容量 int b=cp; //以物品单位重量价值递减序装入物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } //装满背包 if(i<=n) b+=p[i]/w[i]*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp<cp) { for(int j=1;j<=n;j++) bestx[j]=x[j];

bestp=cp; } return; } if(cw+w[i]<=c) //搜索左子树 { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp)//搜索右子树 { x[i]=0; Backtrack(i+1); } } class Object { friend int Knapsack(int p[],int w[],int c,int n); public: int operator<=(Object a)const { } private: int ID; float d; }; int Knapsack(int p[],int w[],int c,int n) {//为 Knap::Backtrack 初始化 return (d>=a.d);

int W=0; int P=0; int i=1; Object *Q=new Object[n]; for(i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c) return P;//装入所有物品 //依物品单位重量排序 float f; for( i=0;i<n;i++) for(int j=i;j<n;j++) { if(Q[i].d<Q[j].d) { f=Q[i].d; Q[i].d=Q[j].d; Q[j].d=f; } } Knap K; K.p = new int[n+1]; K.w = new int[n+1]; K.x = new int[n+1]; K.bestx = new int[n+1]; K.x[0]=0;

K.bestx[0]=0; for( i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0;K.cw=0; K.c=c;K.n=n; K.bestp=0;//回溯搜索 K.Backtrack(1);K.print(); delete [] Q;delete [] K.w; delete [] K.p; return K.bestp; } void main() { int *p;int *w; int c=0;int n=0;int i=0; cout<<"请输入背包个数:"<<endl; cin>>n; p=new int[n+1]; w=new int[n+1]; p[0]=0;w[0]=0; cout<<"请输入各背包的价值:"<<endl; for(i=1;i<=n;i++) cin>>p[i]; cout<<"请输入各背包的重量:"<<endl; for(i=1;i<=n;i++) cin>>w[i]; cout<<"请输入背包容量:"<<endl; cin>>c; cout<<Knapsack(p,w,c,n)<<endl;

}

五、实验结果 1、实验图形

2、结果分析
输入背包个数为 4 个,背包价值分别为 30 25 26 15,背包重量分别为 4 2 3 1, 背包的容量分别为 1 2 3 4,则得出的背包算法为 0 0 0 1,最优值为 15。

3、实验总结
本次的实验过程中,遇到了一些小问题。最终通过百度的方式解决了,同 时也让自己了解到所谓回溯法就是指为了避免生成不可能产生最优解的问题 状态,要不断地利用限界函数 (bounding function)来处死那些实际上不可能产 生所需解的活结点,以此来减少问题的计算量,这种具有限界函数的深度优先 生成法就称为回溯法。 总之通过本次的算法设计的实验,我加深了对算法的设计与分析基础知识 的了解,让自己对算法的掌握更加牢固,也让自己能够熟练的利用 C++语言来 实现算法,同时实践动手能力也得到了一定的提高,做实验确实是一件让人快 速提高动手能力的事情。相信自己以后的实验会做得越来越顺利。


相关文章:
用回溯法解决0-1背包问题.doc
搜试试 5 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 ...用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决...
回溯算法解决0-1背包问题(DOC).doc
回溯算法解决0-1背包问题(DOC) - 《算法分析与设计》 实验报告 2015
回溯法解0-1背包问题实验报告.doc
实验4 一 、实验要求 回溯法解 0-1 背包问题 1.要求用回溯法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。 ...
0-1背包问题的解决(回溯法).doc
回溯法| 背包| 0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题。 前面...
回溯算法解决0-1背包问题.doc
回溯算法解决0-1背包问题 - 《算法分析与设计》 实验报告 2015-2016
回溯法求0-1背包问题.doc
回溯法求0-1背包问题 - 《算法设计与分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量...
回溯法实验(0-1背包问题).doc
回溯法实验(0-1背包问题) - 算法分析与设计实验报告 第五 次附加实验 姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法实验(0-1 背包...
回溯法和分支限界法解决0-1背包题(精).doc
回溯法解决 0-1 背包问题复杂度分析: 计算上界需要 O(n)时间,在最坏情况
回溯法-0-1背包问题.doc
回溯法-0-1背包问题_计算机软件及应用_IT/计算机_专业资料。1、 问题描述 一、0-1 背包问题 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,...
算法分析回溯法实现0-1背包(c++).doc
算法分析回溯法实现0-1背包(c++) - 回溯法) 本程序实现 0-1 背包问题算法 (回溯法) /** 本程序实现 0-1 背包问题算法 (回溯法) **/ #include <iostr...
回溯法和分支限界法解决0-1背包题.doc
搜试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 IT/计算机 ...二、回溯法步骤思想描述: 0-1 背包问题是子集选取问题。0-1 背包问题的解...
0029算法笔记【回溯法】n后问题和0-1背包问题.doc
0029算法笔记【回溯法】n后问题和0-1背包问题 - 1、n 后问题 问题描述
01背包问题回溯算法.doc
搜试试 5 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 专业资料 IT...回溯算法解决背包问题 源... 5页 免费 回溯算法0-1背包问题... 5...
动态规划解决算法0-1背包问题实验报告(含源代码).doc
动态规划解决算法0-1背包问题实验报告(含源代码) - 1.设计一个O(n^2)时间的算法,找出由n个数组成的序列的最长单调递增子序列 2.将算法分析题31中算法的...
回溯算法 0-1 背包算法 c++.doc
搜试试 5 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 专业资料 IT...【实验内容】 用回溯法求解 01 背包问题,并输出问题的最优解。01 背包...
回溯法解决符号三角形与0-1背包问题.pdf
宁夏师范学院数学与计算机科学学院 《算法分析与设计》实验报告实验序号:9 学号姓 实验项目名称:回溯法解决符号三角形与 0-1 背包问题 名 专业、班时间 2014.06....
0_1背包问题的多种解法.doc
搜试试 5 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 专业资料 IT...用回溯法求解 0-1 背包问题的过程 递归法:在利用递归法解决 0-1 背包问题时...
0-1背包问题四种不同算法的实现要点.doc
搜试试 1 悬赏文档 全部 DOC PPT TXT PDF XLS ...0-1背包问题四种不同算法的实现要点_教育学_高等...[i]; 方案三:回溯法 1、回溯法的基本原理与分析...
最新动态规划解决算法0-1背包问题实验报告(含源代码).doc
搜试试 7 帮助 全部 DOC PPT TXT PDF XLS ...最新动态规划解决算法0-1背包问题实验报告(含源...一.实验目的及实验环境 1.使用动态规划法和回溯法...
0-1背包问题的算法设计策略对比与分析报告.doc
搜试试 1 悬赏文档 全部 DOC PPT TXT PDF XLS ...算法设计与分析课程论文 0-1背包问题算法设计策略...回溯法 回溯法的基本做法是搜索,或是一种组织得井...
更多相关标签: