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

算法分析与设计实验报告 第 五 次附加实验 姓名 学号 班级 时间 12.26上午 地点 工训楼309 实验名称 回溯法实验(0-1背包问题) 实验目的 掌握回溯法求解问题的思想 学会利用其原理求解0-1背包问题 实验原理 基本思想： 0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。 基本解题步骤： 针对所给问题，定义问题的解空间； 确定易于搜索的解空间结构； 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 实验步骤 （1）首先搜索解空间树，判断是否到达了叶结点； （2）如果左子结点是一个可行节点，就进入左子树； （3）当右子树有可能包含最优解的时候才进入右子树，计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包； （4）利用深度优先搜索整个解空间树，直到将所有的最优解找出位置。 关键代码 templateclass Typew,class Typep void KnapTypew,Typep::Backtrack(int i) { if(in) //到达叶子节点 { bestp = cp; //更新最优值 return; } if(cw + w[i] = c) //进入左子树 { cw += w[i]; cp += p[i]; Backtrack(i+1); //回溯 //回溯结束回到当前根结点 cw -= w[i]; cp -= p[i]; } //进入右子树，条件是上界值比当前最优值大，否则就将右子树剪掉 if(Bound(i+1)bestp) { Backtrack(i+1); } } 测试结果 当输入的数据有解时： 当输入的数据无解时： 当输入的数据稍微大点时： 实验分析 在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我们只需要验证该程序是否正确即可。0-1背包问题和之前的最优装载其实质上一样的，都是利用解空间树，通过深度优先搜索子集树，通过利用上界函数和一些剪枝策略，从而得到最优解。由于数据较小，所以时间上并不能反映出什么东西。 实验心得 在这一章的回溯算法中，我们用的比较多的就是；利用子集树来进行问题的探索，就例如上图是典型的一种子集树，在最优装载、0-1背包都是利用了这种满二叉树的子集树进行求解，然后通过深度优先的策略，利用约束函数和上界函数，将一些不符合条件或者不包含最优解的分支减掉，从而提高程序的效率。对于0-1背包问题我们基本上在每一个算法中都有这么一个实例，足以说明这个问题是多么经典的一个问题啊，通过几个不同的算法求解这一问题，我也总算对该问题有了一定的了解。 实验得分 助教签名 附录： 完整代码（回溯法） //0-1背包问题 回溯法求解 #include iostream using namespace std; templateclass Typew,class Typep class Knap //Knap类记录解空间树的结点信息 { templateclass Typew,class Typep 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; //当前价值