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

算法分析与设计实验报告第 五 次附加实验姓名学号班级时间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(in) /到达叶子节点 bestp = cp; /更新最优值 return; if(cw + wi 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 ;/背包容量 coutn;coutc;int *p = new intn;/物品价值 下标从1开始 int *w = new intn;/物品重量 下标从1开始 cout物品重量分别为：endl; for(int i=1; iwi; cout物品价值分别为：endl;for(int i=1; ipi; cout物品重量和价值分别为：endl; for(int i=1; i=n; i+) /以二元组（重量，价值）的形式输出每个物品的信息 cout(wi,pi) ; coutendl; cout背包能装下的最大价值为：Knapsack(p,w,c,n)endl; /输出结果system(pause); return 0; template void Knap:Backtrack(int i) if(in) /到达叶子节点 bestp = cp; /更新最优值 return; if(cw + wi bestp) Backtrack(i+1); template Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 如果背包剩余容量不足以装下一个物品 if (i = n) b += pi/wi * 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 Objectn;/创建Object类的对象数组 /初始化Object类的对象数组 for(int i=1; i=n; i+) Qi-1.ID = i; Qi-1.d = 1.0 * pi/wi; P += pi; W += wi; if(W = c)/装入所有物品 return P; /依物品单位重量价值降序排序 BubbleSort(Q,n); Knap K; /创建Knap的对象K K.p = new Typepn+1; K.w = new Typewn+1; for(int i=1; i=n; i+) K.pi = pQi-1.ID; K.wi = wQi-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; in-1;i+) exchange = false ; for(int j=i+1; j=aj-1)