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

《回溯法实验(0-1背包问题).pdf》由会员分享，可在线阅读，更多相关《回溯法实验(0-1背包问题).pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计实验报告 第 五 次附加实验 姓名 学号 班级 时间 上午 地点 工训楼 309 实验名称 回溯法实验(0-1 背包问题)实验目的 1.掌握回溯法求解问题的思想 2.学会利用其原理求解 0-1 背包问题 实验原理 基本思想：0-1 背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。基本解题步骤：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

2、。实验步骤 （1）首先搜索解空间树，判断是否到达了叶结点；（2）如果左子结点是一个可行节点，就进入左子树；（3）当右子树有可能包含最优解的时候才进入右子树，计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包；（4）利用深度优先搜索整个解空间树，直到将所有的最优解找出位置。关键代码 template void Knap:Backtrack(int i)if(in)D=i;Qi-1.d=*pi/wi;P+=pi;W+=wi;if(W=c)D;i=wQi-1.ID;/初始化K =0;=0;=c;=n;=0;/回溯搜索 (1);del

3、ete Q;delete;delete;return;/返回最优解 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)Swap(aj,aj-1);exchange=true;/如果这次遍历没有元素的交换，那么排序结束 if(exchange=false)break;template inline void Swap(Type&a,Type&b)/交换函数 Type temp=a;a=b;b=temp;