实验4回溯算法.docx

《算法设计与分析》实验报告实验 4回溯算法姓名学号班级网络 131 实验日期 实验地点学院 305 一、实验目的 1、掌握分治算法的设计思想与分析方法; 2、掌握归并排序、快速排序等高效排序算法。二、实验环境 1 、硬件环境 CPU : IntelR coreTM i5-3337U 内存: 硬盘: 1TB 2 、软件环境操作系统: win10 编程环境: C Free 编程语言: C三、实验内容 1 、问题有一个背包,最大限重为 C,有 n 个物品,重量分别为 W=<w 1,w 2,…,w n>, 要求找出一个装载方案,使得放入背包物品的重量最大。输出装载方案和该方案下的背包所装物品总重量。 2 、数据结构(1)解的结构一维数据(1) <010111 1> (2) <001011 0> (2)搜索空间的结构 3 、算法伪代码 ReBack(i) 1、 If i>n then<x1,x2,x3,...xn> 是解 2、 Else while Si≠? do 3、 Xi<— Si中最小值 4、 Si< —Si-{Xi} 5、计算Si+1 6、 ReBack (i+1 )4 、算法分析时间复杂度: O(2n) 空间复杂度: O(n) 5 、关键代码(含注释) #include <iostream> #include <vector> using namespace std; class PackBackTrack { protected: vector<int> m_p; //N 个背包的价格 vector<int> m_w; //N 个背包的重量 int m_c; //背包的容量 int m_num; //物品的件数 int bestValue; //背包最大价值 int currentValue; //当前背包中物品的价值 int currentWeight; //当前背包中物品的重量 private: //辅助函数,用于回溯搜索 void BackTrack(int depth) { if(depth >= m_num) //达到最大深度{ if(bestValue < currentValue) //保存最优解 bestValue = currentValue; return ;} if(currentWeight +m_w[depth] <= m_c) //是否满足约束条件{ currentWeight += m_w[depth]; currentValue += m_p[depth]; //选取了第 i件物品 BackTrack(depth+1); //递归求解下一个结点//恢复背包的容量和价值 currentWeight -= m_w[depth]; currentValue -= m_p[depth]; } //不取第 i件物品 BackTrack(depth+1); } public: //构造函数 PackBackTrack(); PackBackTrack(vector<int>& p,vector<int>& w, int c,int n) :m_p(p),m_w(w),m_c(c),m_num(n) { bestValue =0; currentValue =0; currentWeight =