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

1、算法分析与设计实验报告第五个附加实验姓名学生身份证班级时间上午12时26分位置龚勋309大楼实验名称回溯实验(0-1背包问题)实验目的1.掌握回溯法解决问题的思想2.学会用它的原理来解决0-1背包问题实验原理基本思想：0-1背包问题是一个子集选择问题。0-1背包问题的解空间可以用子集树来表示。当搜索解空间树时，只要其左子节点是可行节点，搜索将进入左子树。当右子树可能包含最优解时，进入右子树的搜索。否则，切掉右边的子树。解决问题的基本步骤：(1)对于给定的问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)深度优先搜索解空间，使用剪枝函数避免无效搜索。实验步骤(1)首先搜索解空间树，判

2、断是否到达叶节点；(2)如果左边的子节点是可行节点，则进入左边的子树；(3)当右子树可能包含最优解时，它将进入右子树。计算右子树上限的一个更好的方法是将剩余的物品按照它们的单位值依次排序，然后依次装入它们，直到它们不能容纳，然后装入一些物品来装满背包；(4)首先用深度搜索整个解空间树，直到找到所有最优解。键盘编码器模板无效knap:backtrack回溯(int i)如果(in) /到达叶节点bestp=cp。/更新最佳值返回；如果(cw wi=c) /输入左边的子树cw=wi；cp=pi；回溯(i 1)；/回溯/回溯后返回当前根节点cw-=wi；cp-=pi；/输入右子树，前提是上限值大于当

3、前最优值，否则，切断右子树。如果(约束(i 1)最佳)回溯(i 1)；试验结果当输入数据有解决方案时：当输入数据没有解决方案时：当输入数据稍大时：实验分析在实验中，我们没有生成多组数据进行比较，也没有使用随机生成函数，因为在这个实际相关的问题中，使用随机生成函数生成数据是非常不合适的，所以我们只需要验证程序是否正确。0-1背包问题本质上与以前的最优装载相同，它使用解空间树，先搜索有深度的子集树，然后使用上界函数和一些剪枝策略得到最优解。因为数据很小，时间不能反映任何东西。实验经验在本章的回溯算法中，我们使用了更多；使用子集树来探索问题，例如，上图是一个典型的子集树，用于解决最优装载和0-1背包

4、问题。然后，通过深度优先策略，利用约束函数和上界函数减去一些不满足条件或不包含最优解的分支，从而提高程序的效率。对于0-1背包问题，我们基本上在每个算法中都有这样一个例子，这足以说明这个问题有多经典。通过几种不同的算法解决了这个问题之后，我终于对这个问题有了一定的了解。实验分数助教签名附录：完整代码(追溯方法)/用回溯法解决0-1背包问题#包括使用命名空间标准；模板类knap /knap类记录解空间树的节点信息模板朋友类型背包(类型，类型，类型，整数)；private:打字装订(国际)；/计算上限函数无效回溯(int i)；/通过回溯找到最优解函数c型。/背包容量int n；/项目数键入w *

5、w。/项目权重数组p型*p。/项目值数组cw型。/当前重量cp型。/当前值键入bestp。/当前最终值；模板背包式(p型，w型，c型，整数型)；/声明背包问题求解函数模板线内无效交换(a类，b类)；/声明交换函数模板无效气泡开始(类型a，整数n)；/声明冒泡排序功能int main()int n；/项目数int c；/背包容量项目数为：；cinncout的背包容量为：；cincint *p=新intn；/项目值下标从1开始int *w=新intn；/物品重量指数从1开始文章的重量是：“wi；“商品的价值是：pi；物品的重量和价值是：无效knap:backtrack回溯(int i)如果(in)

6、 /到达叶节点bestp=cp。/更新最佳值返回；如果(cw wi=c) /输入左边的子树cw=wi；cp=pi；回溯(i 1)；/回溯/回溯后返回当前根节点cw-=wi；cp-=pi；/输入右子树，前提是上限值大于当前最优值，否则，切断右子树。如果(约束(i 1)最佳)回溯(i 1)；模板typepknap : bound(int i)/计算上限w型裂缝=c-cw；/剩余容量类型b=cp。/按单位重量值的降序加载项目而(i=n wi=裂缝)裂缝-=wi；b=pi；i ./如果背包的剩余容量不足以容纳下一个物品，if (i=n)b=pi/wi *裂缝；/将物品的一部分放入背包返回b；类对象/定

7、义对象类，它作为一个结构模板朋友类型背包(类型，类型，类型，整数)；public:int运算符=(对象a)常量/符号重载函数，重载=符号返回(d=a . d)；private:内部标识；/没有浮动d；/单位重量值；模板背包式(p型，w型，c型，整数)/初始化knap:backtrack回溯类型w=0；类型p=0；对象*q=新对象n；/创建对象类的对象数组/初始化对象类的对象数组for(int i=1；i=n；i)qi-1。id=i。qi-1。d=1.0 * pi/wi；p=pi；w=wi；如果(w=c)/加载所有项目返回p；/按项目单位重量值降序排列起泡点(q，n)；knap k；/创建knap的对象kk.p=新typepn1；k.w=新类型wn1；for(int i=1；i=n；i)k.pi=pqi-1。身份证；k.wi=wqi-1。身份证；/初始化k。k . cp=0；k . cw=0；k.c=c。k.n=n。k.bestp=0。/回溯搜索k.回溯(1)；删除q；删除k . w；删除k . p；返回k.bestp/返回最优解模板无效气泡开始(类型a，整数n)/记录一次遍历中