回溯法实验(0-1背包问题).doc

(8页)

'回溯法实验(0-1背包问题).doc'
?算法分析与设计实验报告第 五 次附加实验姓名学号班级时间12.26上午地点工训楼309 实验名称回溯法实验(0-1背包问题)实验目的1. 掌握回溯法求解问题的思想2. 学会利用其原理求解0-1背包问题实验原理基本思想:0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时,只要其左儿子节点是一个可行节点,搜索就进入左子树。当右子树中有可能含有最优解时,才进入右子树搜索。否则,将右子树剪去;窘馓獠街:(1) 针对所给问题,定义问题的解空间;(2) 确定易于搜索的解空间结构;(3) 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。实验步骤(1)首先搜索解空间树,判断是否到达了叶结点;(2)如果左子结点是一个可行节点,就进入左子树;(3)当右子树有可能包含最优解的时候才进入右子树,计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序,然后依次装入物品,直至装不下时,再装入物品一部分而装满背包;(4)利用深度优先搜索整个解空间树,直到将所有的最优解找出位置。关键代码template void Knap::Backtrack(int i) { if(i>n) //到达叶子节点 { bestp = cp; //更新最优值 return; } if(cw + w[i] bestp) { Backtrack(i+1); } }测试结果 当输入的数据有解时: 当输入的数据无解时: 当输入的数据稍微大点时:实验分析在实验中并没有生成多组数据,进行比较,也没有利用随机生成函数,因为在这种有实际有关联的问题中,利用随机生成函数生成的数据是十分的不合适的,在此我们只需要验证该程序是否正确即可。0-1背包问题和之前的最优装载其实质上一样的,都是利用解空间树,通过深度优先搜索子集树,通过利用上界函数和一些剪枝策略,从而得到最优解。由于数据较小,所以时间上并不能反映出什么东西。实验心得在这一章的回溯算法中,我们用的比较多的就是;利用子集树来进行问题的探索,就例如上图是典型的一种子集树,在最优装载、0-1背包都是利用了这种满二叉树的子集树进行求解,然后通过深度优先的策略,利用约束函数和上界函数,将一些不符合条件或者不包含最优解的分支减掉,从而提高程序的效率。对于0-1背包问题我们基本上在每一个算法中都有这么一个实例,足以说明这个问题是多么经典的一个问题啊,通过几个不同的算法求解这一问题,我也总算对该问题有了一定的了解。实验得分助教签名附录:完整代码(回溯法)//0-1背包问题 回溯法求解 #include using namespace std; template class Knap //Knap类记录解空间树的结点信息{ template friend Typep Knapsack(Typep [],Typew [],Typew,int); private: Typep Bound(int i); //计算上界的函数 void Backtrack(int i); //回溯求最优解函数 Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组? Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template Typep Knapsack(Typep p[],Typew w[],Typew c,int n); //声明背包问题求解函数template inline void Swap(Type &a,Type &b); //声明交换函数template void BubbleSort(Type a[],int n); //声明冒泡排序函数int main() { int n ;//物品数 int c ;//背包容量 cout<>n; cout<>c; int *p = new int[n];//物品价值 下标从1开始 int *w = new int[n];//物品重量 下标从1开始 cout<<"物品重量分别为:"<<endl; for(int i=1; i>w[i]; } cout<<"物品价值分别为:"<<endl; for(int i=1; i>p[i]; } cout<<"物品重量和价值分别为:"<<endl; for(int i=1; i<=n; i++) //以二元组(重量,价值)的形式输出每个物品的信息 { cout<<"("<<w[i]<<","<<p[i]<<") "; } cout<<endl; cout<<"背包能装下的最大价值为:"<<Knapsack(p,w,c,n)<<endl; //输出结果 system("pause"); return 0; } template void Knap::Backtrack(int i) { if(i>n) //到达叶子节点 { bestp = cp; //更新最优值 return; } if(cw + w[i] bestp) { Backtrack(i+1); } } template Typep Knap::Bound(int i)// 计算上界 { Typew cleft = c - cw; // 剩余容量 Typep 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; } class Object //定义对象类,作用相当于结构体{ template friend Typep Knapsack(Typep[],Typew [],Typew,int); public: int operator >= (Object a)const //符号重载函数,重载>=符号 { return (d>=a.d); } private: int ID; //编号 float d; //单位重量的价值 }; template Typep Knapsack(Typep p[],Typew w[],Typew c,int n) { //为Knap::Backtrack初始化 Typew W = 0; Typep P = 0; Object *Q = new Object[n];//创建Object类的对象数组? //初始化Object类的对象数组? for(int 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; } //依物品单位重量价值降序排序 BubbleSort(Q,n); Knap K; //创建Knap的对象K K.p = new Typep[n+1]; K.w = new Typew[n+1]; for(int i=1; i<=n; i++) { K.p[i] = p[Q[i-1].ID]; K.w[i] = w[Q[i-1].ID]; } //初始化K K.cp = 0; K.cw = 0; K.c = c; K.n = n; K.bestp = 0; //回溯搜索 K.Backtrack(1); delete []Q; delete []K.w; delete []K.p; return K.bestp; //返回最优解} template void BubbleSort(Type a[],int n) { //记录一次遍历中是否有元素的交换 bool exchange; for(int i=0; i<n-1;i++) { exchange = false ; for(int j=i+1; j=a[j-1]) { Swap(a[j],a[j-1]); exchange = true; } } //如果这次遍历没有元素的交换,那么排序结束 if(exchange==false) { break ; } } } template inline void Swap(Type &a,Type &b) //交换函数{ Type temp = a; a = b; b = temp; }
关 键 词:
实验 背包 问题 回溯
 剑锋文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:回溯法实验(0-1背包问题).doc
链接地址: //www.wenku365.com/p-55128648.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给剑锋文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 //www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开