算法设计实验报告讲解

时间：2020-09-29 11:37:49 来源：蒲公英阅读网 本文已影响人

相关热词搜索：算法 讲解 实验

　华北电力大学 实验报告 | | 实验名称 ____ 算法设计与分析综合实验 ________________

　课程名称 _______ 算法设计与分析 __________________

　| | 专业班级：

　学生姓名：

　学 号：

　指导教师：

　[综合实验一]分治策略一归并排序 一、 实验目的及要求 归并排序是一个非常优秀的排序方法 ， 也是典型的分治策略的典型应用。

　实验要求：

　( 1 编写一个模板函数：

　template vtypename T> , MergeSort(T *a, int n); 以及相应的 一系列函数，采用分治策略，对任意具有 ：

　bool operator<(const T&x,const T&y) 比较运算符 的类型进行排序。

　(2) 与 STL 库中的函数 std::sort(..) 进行运行时间上的比较，给出比较结果 ， 如：动态 生成100 万个随机生成的附点数序列的排序列问题 ， 给出所用的时间比较。

　二、 所用仪器、设备 计算机、 Visual C+ 嗽件。

　三、 实验原理 分治原理：

　分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些 子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。当我们 求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接 求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解 成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求 整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子 问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

　归并原理：

　归并排序是建立在归并操作上的一种有效的排序算法 ， 该算法是采用分治法( Divide and Conquer )的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列； 即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称 为二路归并。

　四、 实验方法与步骤 归并过程为：比较 a[i] 和 a[j] 的大小，若 a[i] < a[j] 则将第一个有序表中的元素 a[i] 复 制到 r[k]中，并令 i 和 k 分别加上 1 ;否则将第二个有序表中的元素 a[j] 复制到 r[k] 中，并 令 j 和 k 分别加上1 ,如此循环下去，直到其中一个有序表取完， 然后再将另一个有序表 中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。归并排序的算法我们通常用递归实 现，先把待排序区间 [s,t] 以中点二分，接着把左边子区间排序，再把右边子区间排序， 最 后把左区间和右区间用一次归并操作合并成有序的区间 [s,t] 。

　实现时间计量：

　#defi ne _CLOCK_T_DEFINED sran d(( un sig ned)time(O)); // 定义一数组 a[n]; 对每一个赋予一值。

　a[i]=ra nd(); 得到随即数。

　duration =(double)(finish -start)/CLOCKS_PER_SEC; start=clock() 将系统时间赋予 Start 。以便以后进行比较。

　std::sort(b,b+1000); 系统执行 1000 个数据。

　Fi ni sh-Start 为最终结果。

　五、 实验结果与数据处理

　实验结果截图：

　■"D;\Program Files\VC + + 6 H O\MSDev98\Bin\Debug\1 exe* 慎輪入; t 專卡致：

　160 叛组己建立：

　盹翌庠 F曲扫并数组：

　2&72^.2 2^395.2 30062 1 12511 ， & 1 09. 1166 €1 31MGS 3 1^865.7 818&.58 32?55 23766.5 7793,?2 S ：

　28 G9 1 >I32S 3 2GSG5.6 1 7TS3 9 2C253.1 10590 .? 10451 .5 £743.& 26625.7 36802 2 B299.59 2478G.2 31THT.9 1421,77 2€288.7 2723H 5 19788.7 8383.3 5533.92 13Q63.T 1T82S.3 29397.1 1 05H2. 2G TSS.1 28389.7 12235.1 94H5.21 1897.38 S41 7 S7 3174.21 2491 E . 8 11535, 3 77.576? 32511.7 1 T7S4 .5 27B54. € 1T<+5S H 26 &93 69^4.77 1168C. 1 2 刑 32292.3 12187

　3321 . 1257& 5 15283.2 2GE3Q 3 32719,5 T75.2B3 19325 a 1B631 ,1 2H&49. 9 313e*i. 5 1D€35 .& 12867,44 1 .s 22S3B r 9SS9 52 ZM5S3 12087 1HE5E.1 11697,4 20A+9Q.G 26-931 a 17381 . 1 19&74 18494,2 3533,12 2BT4G.3 51«5 .38

　22103.1 坪斗 24 . ? 2246T 1 11G-4.3 r 123G7.3 18729.1 2276

　284S9 9 283H 9S12.23 19063. 2 883G <43

　-^.22017*+037 2SF58 1 2050 9 ?B^I2.03 辎入翕翌昱示的排停方汕£ 1 .归并排序 玄上 ttl 汗序 持庁门的仔列询：

　Tr.srer 31 78.21 TP42 es S812.23 1 1 535.3 1 25 76.5 1 73S1 . 1 1 9325.8 22^r. 1 262SJ. 1 27234.5 30062. 1 103 H 775.263

　SZ®.69 1 3321,04 3533.1 2 4424 . T 7795,3? 318? \50 9239.59 9899.52 1M41 . 8 10HG1.5 11 S&S.l 1 203 7

　1 2996.9 123CT.4 1SGG3 ? 13G5G.1 1T455.4 1 7T54 5 17736.9 197&8.7 1987M

　^0^25. ? 22850.7 23TGG 5 站 593 2S2S8.T 26 £39 3 2G?2G 2 ZT65*I.G 283GG H 2B3B9,7 阳收 30862.2

　31 3Q>t.5

　32719.5 32255 32511 丄 M#rgScrti^4 亍了* 创 熊入裔薩昌示的排手方法 J 1 .阳并排序 2-std 排序 挖罠冇严-前入法 全 ； 160 5185.30 i ^17 97 1C542.3 1Z18F 12255.1 1Z3E7.3 114323.3 1<4£€5 T i 17&28.3 1S451F 2 26QS& 斗 24&He.S 24786.2 26 7*16.3 26TS9 1 284S9.9 28758 31<+€5.4 31463.3 -4,2201 7*+637 1 16*1 ST 5533.92 165^9.7 1<t21 . ?7 1B9T 3® G743 G G3*l>l . 77 5896,43 21 1Q635. E 1 1G97.-H 12511 £ 152&3.2 1GQ31.1 13729.1 19BG6.2 £6499.6 1 24809,2 2491&.« 2S3&S.G 26991.9 2S898 29397.1 31747.9 322Q2.9

　输入需要显示的排序方法: 「归弄排序 2std 排序 0 一退出 77.5767 3178.21 7642.03 3812.23 11535 3 12576.5 1 7381 . 1 1 3325.3 224G7 1 2G253 1 27234.5 30Q62.1 32255 std ：

　：

　169.4

　3321.04 7703.32 9393.52 11G86.1 12867.4 1 74S5.4 19785.7 22830.7 26258.7 27654.6 30^£6 325J 1^7 ：$。广 1运行了：

　9ms 775,263 328,G9 1160.61 5195.38 8*+1 7.97 105H2 3 121S7 14328.3 17828.3

　2003S 2H6^9.9 2G7H& 3 4424.7 8299.59 10H61I . 5 12G3D.9 1164.37 1^21,77 139T.3S 2276.6 6TH3.6 69^H.?7 3836.*+3 9^45.21 ie&35.e 11097.>+ 12511.6 16031.1 19660.2 22103.1 2491S ® 26391.9 3533.1 2 81@6.58 164>+1 E 12GS7 12G9D.9 121S7 12255 1 12367.3 13063.F 13656.1 14328.3 14365,7 152S3.2 1775^.5 l7FSO r 9 1782S.3 1S^5H.2 18729.1 1S87>+ 20325.7 2003S 2043G .€ 20H9Q. G 2376G.5 24593 2H6*+9.9 24 7SG.2 24809 2 2G£3G.3 2G72G.2 2G7HG 3 26799.1 £ES£5.e 23306.4 28339? 2S4S9.9 2S758 28893 29397.1 3G802.2 32719.5 5533.92 BS83.3 10590 T 31334.5 31^G5.H 31M69.3 31747.9 32292.3 -*♦ . 22017s + D3T 齣入需更显示的拌序方法：

　「归并排序 2, & td 排序 0 Press any keij to continue

　 #in clude<iostream.h> #i nclude<algorithm> #in clude<time.h> #in clude<stdio.h> #in clude<stdlib.h> using n amespace std; templatevclass Type> void MergSort(Type a[], int n){ Type *b = new Type [n]; int s = 1; while (s < n){ MergPass(a, b, s, n); s += s; MergPass(b, a, s, n); s += s; } } templatevclass Type> void MergPass(Type x[], Type y[], int s, int n) { int i = 0; while (i <= n - 2 * s) { Merg(x, y, i, i + s - 1, i + 2 * s - 1); i = i + 2 * s;if (i + s < n) Merg(x, y, i, i + s - 1, n - 1); else{ for (int j = i; j <= n - 1; j++){ y[j] = x[j]; }

　}

　} template<class Type> void Merg(Type c[], Type d[], int l, int m, int r){ int i = l, j = m + 1, k = l; while ((i <= m) && (j <= r)){ if (c[i] <= c[j]) d[k++] = c[i++]; else d[k++] = c[j++]; 实验代码:

　}

　if (i>m) for (int q = j; q <= r; q++) d[k++] = c[q]; else for (int q = i; q <= m; q++) d[k++] = c[q]; }

　float randf(float base, float up){ return (rand() % (int)((up - base) * RAND_MAX))/(float)RAND_MAX ; // 产生随机数 }

　void printArray(float *a,int N){ for(int i=0;i<=N;i++){ if((i%8==0)&&(i>0)) { cout<<a[i]<<endl; }

　else{ cout<<a[i]<<" "; }

　}

　}

　void main(){ int ArrayLen = 5; cout<<" 请输入元素个数：

　"<<endl; cin>>ArrayLen; float *array = new float[ArrayLen]; float *arrays = new float[ArrayLen]; float mn, ene;

　printf(" 数组已建立：

　\n"); srand((unsigned)time(NULL)); // 设置随机数的 seed for (int i = 0; i < ArrayLen; i++) {

　mn = (float)rand(); // 产生小数 ene = randf(1,10000)+mn; arrays[i] =ene; array[i] = ene; }

　//cout<<" 需要排序的归并数组 :\n"; //printArray(array, ArrayLen); int flag = 1; while (flag != 0){ cout<<"\n 输入需要显示的排序方法：

　"<<endl; cout << "1.归并排序 2.std 排序 0.退出"<< endl; cin >> flag; switch (flag){ case 0: break; case 1: {

　clock_t s = 0, e = 0; s = clock(); MergSort(array, ArrayLen); e = clock(); //cout<<" 排序后的序列为：

　"<<endl; //printArray(array, ArrayLen); cout << "\nMergSort 运行了：

　" << (e - s) << "ms" << endl; break; }

　case 2:{ clock_t start1 = 0, end1 = 0; start1 = clock(); std::sort(&arrays[0], &arrays[ArrayLen]); end1 = clock(); //printArray(array, ArrayLen); cout << "\nstd::sort 运行了：

　" << (end1 - start1) << "ms" << endl; break; }

　}

　}

　}

　［综合实验 二］贪心算法一 Huffman 树及 Huffman 编码 一、 实验目的及要求 一个记录字符及出现频率的文件如下所示：

　huffma n.haf 7 a, 45 b, 13 c, 12 d, 16 e, 89 f, 34

　g, 20 试编写一个读取此种格式文件类 CHuffman, 内部机制采用优先队列，用于建立 Huffman 树及进行 Huffman 编码输出，其用法可以如下所示：

　CHuffma n hm("huffma n.dat"); hm.CreateTree(); hm.OutputTree(); hm.OutputCode(); // 二进制形式的字符串 对于输出树的形式可自行决定 ( 如图形界面或字符界面 ) 。

　二、 所用仪器、设备 计算机、 Visual C+ 嗽件。

　三、 实验原理 贪心原理：

　(1) 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的 候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

　(2) 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑 此时的解决方法是否最优。

　(3) 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合 上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优 性。

　(4) 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

　(5) 最后，目标函数给出解的值。

　(6) 为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数， 贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。

　接下来的每一步中, 根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该 对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集 合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最 优的。

　Huffman 原理：

　给定 n 个权值作为 n 的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称 这样的二叉树为最优二叉树，也称为哈夫曼树 (Huffman tree) 。哈夫曼树是带权路径长度 最短的树，权值较大的结点离根较近。

　四、实验方法与步骤 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T 。算法以个叶结点开 始，执行次的 合并”运算后产生最终所要求的树 T 。给定编码字符集 C 及其频率分布 f ， 即 C 中任一字符 c 以频率 f ( c )在数据文件中出现。

　C 的一个前缀码编码方案对应于一 棵二叉树 T 。字符 c 在树 T 中的深度记为。也是字符 c 的前缀码长。

　该编码方案的平均码长定义为：

　B ( T )使平均码长达到最小的前缀码编码方案称为 C 的一个最优前缀码。一旦两棵具有最小频率的树合并后，产生的一颗新的树，起频率 为合并的两棵树的频率之和，并将新树插入优先队列中。

　优先队列，优先队列是 0 个或多个元素的集合 , 每个元素都有一个优先权或值 , 对优先 队列执行的操作有 1) 查找 ;2) 插入一个新元素 ;3) 删除 . 在最小优先队列 (min priority queue) 中 ， 查找操作用来搜索优先权最小的元素 ， 删除操作用来删除该元素 ； 对于最大优先 队列 (max priority queue), 查找操作用来搜索优先权最大的元素 ， 删除操作用来删除该元素 . 优先权队列中的元素可以有相同的优先权 , 查找与删除操作可根据任意优先权进行 . 五、实验结果与数据处理 主要代码如下：

　Huffman::Huffman(char *sFileName1) {

　this->sFileName = sFileName1 ； ifstream fin(sFileName) ；

　char ch[4] ； fin.getline(ch, 4) ； int n1 = atoi(ch) ； cout << " 节点数目 : "<<n1 << endl ； this->n = n1 ； this->t = new THaffmanNode[2 * n1 - 1] ；

　this->nNext = n1 ；

　char ch1 ；

　for (int i = 0 ；

　i<n1 ；

　i++) {

　fin.get(ch1) ； t[i].c = ch1 ； fin.ignore(100, ",") ；

　fin.getline(ch, 4) ；

　t[i].f = atoi(ch) ； }

　for (int i = 0 ；

　i<n ；

　i++) {

　cout << t[i].c << " " << t[i].f << endl ； }

　for (int i = 0 ；

　i<n ；

　i++) {

　t[i].idx = i ； PQ.push(t[i]) ；

　while (!PQ.empty()) {

　if ((PQ.size()) >= 2) { THaffmanNode nn, nr, nl; nl = PQ.top(); PQ.pop(); nr = PQ.top(); PQ.pop(); nn.f = nl.f + nr.f; nn.l = nl.idx; nn.r = nr.idx; nn.idx = nNext++; t[nl.idx].p = nn.idx; t[nr.idx].p = nn.idx; t[nn.idx] = nn; PQ.push(nn); }

　else {

　t[2 * n - 2].p = -1; break; }

　}

　}

　Huffman::~Huffman(void) {

　}

　void Huffman::OutputTree() {

　for (int i = 0; i<2 * n - 1; i++) {

　cout << " 权重：

　" << t[i].f << " "; cout << " 左孩子：

　" << t[i].l << " "; cout << " 右孩子：

　" << t[i].r << " "; cout << " 父节点：

　" << t[i].p << " "; cout << " 在数组的位置：

　" << t[i].idx << endl; }

　// 现在数组中存的是哈弗曼数 }

　void Huffman::OutputCode() {

　// 用 stack 来依次记录各编码的 0 1 编码 std::stack<int, std::list<int>> sk; THaffma nN ode n temp, n tempi; for (i nt i = 0; i<n; i++) { n temp = t[i]; while (n temp.p != -1) { n temp1 = t[n temp.p]; if (t[ ntemp1.l].idx == n temp.idx) { sk.push(O); n temp = n temp1; } else {

　sk.push(1); n temp = n temp1; } } int i1 = sk.size(); cout << t[i].f << " : "; for (int i = 0; i<i1; i++) { cout << sk.top(); sk.pop(); } cout << en dl; } } 实验结果截图：

　［综合实验三］ 用回溯方法求解 n 后问题 、实验目的及要求 问题：对任意给定的 n 求解 n 后问题。

　具体要求：

　1. 封装 n 后冋题为类，编写以下两种算法进行求解：

　(1) 递归回溯方法； (2) 迭代回溯方法。

　( 选 ) 2. 对任意给定的 n ,要求输出其解向量(所有解)，并输出其解数; 3.

　构造 n 后问题的解数表格(由程序自动生成) ：

　n 后数 解数 第一个解 4 2 (2,4,1,3) 5 … … 6 … … … … … 二、 所用仪器、设备 计算机、 Visual C+ 嗽件。

　三、 实验原理 回溯原理：

　回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想 是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决冋 题的一般步骤为：

　1 、 定义一个解空间，它包含问题的解。

　2 、 利用适于搜索的方法组织解空间。

　3 、 利用深度优先法搜索解空间。

　4 、 禾 U 用限界函数避免移动到不可能产生解的子空间。

　问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重 要特性。

　四、 实验方法与步骤 n 后问题等于在 n X n 格的棋盘上放置 n 个皇后，任何 2 个皇后不放在同一行或同一 列或同一斜线上。即规定每一列放一个皇后，不会造成列上的冲突；当第 i 行被某个皇 后占领后，贝侗一行上的所有空格都不能再放皇后，要把以 i 为下标的标记置为被占领 状态。

　K :第 K 个皇后，也表示第 K 行 X[i] :第 K 个皇后在第 K 行的第 i 列 皇后 k 在第 k 行第 x[k] 列时， x[i]==x[k] 时，两皇后在同一列上 ； abs(x[i]-x[k])==abs(i-k) 时，两皇后在同一斜线上 ； 两种情况两皇后都可相互攻击，返回 false 表示不符合条件。

　五、 实验结果与数据处理 实验结果截图：

　■ " "D;\Program FilesWC*+6.0\MSL “阳 H.巩迎进入立后问题 请槪入空后敷 2 4 13 .Ik ・ L .It. 3 1 4 2 方宰个块” 2 隧窖劉魚 1 妁是.P 为否 1 甬術入呈后歎 5 1 3 2 >1 It .... ..M .. ...-* tt…* ...It. H… ， ， 上… …鼻 .M ,. …札 ..M ,. ....# 扒.， ...# ..#.. M .... 实验代码：

　#i nclude<iostream.h> #in clude<math.h> class Quee n { friend int n Quee n(i nt); private: bool Place(i nt k); void Backtrack© nt t); int n,*x; // 当前解 long sum; // 当前已找到的可行方案数 }; bool Quee n::Place(i nt k) { for (i nt j=1;j<k;j++) if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; void Queen::Backtrack(int t) {

　if (t>n) { sum++;// 达到叶结点 for(int i=1;i<=n;i++) {

　cout<<x[i]<<" ";

　}

　cout<<endl; for(i=1;i<=n;++i) {

　for(int j=1;j<=n;++j) { if(x[i]!=j) cout<<"." ; else cout<<"#"; }

　cout<<endl; }

　cout<<endl; }

　else for (int i=1;i<=n;i++) { // 搜索子结点 x[t]=i; // 进入第 i 个子结点 if (Place(t)) Backtrack(t+1); }

　}

　int nQueen(int n) {

　Queen X; // 初始化 X X.n=n; X.sum=0; int *p=new int [n+1]; for(int i=0;i<=n;i++) p[i]=0; X.x=p; X.Backtrack(1); // 对整个解空间回溯搜索 delete []p; return X.sum; }

　void main() {int a=O,b=O; coutvv"******** 欢迎进入皇后问题 *********"<<endl; int flag=1; while(flag){ cout«" 请输入皇后数 "<<endl; cin> >a; b=n Quee n( a); cout«" 方案个数：

　"<<b<<e ndl; coutvv" 是否继续？ 1 为是， 0 为否 "<<endl; cin> >flag; } }

　[综合实验四] 背包问题的贪心算法 一、实验目的及要求 问题 ：

　给定如下 n 种物品的编号，及其价值；背包重量为 c, 求最佳装包方案，才能使其装 入背包的价值最大。

　物口口编号11 2 … n 重量 w[1] w[2] ・・ w[ n] 价值 v[1] v[2] … v[n] 具体要求：

　将背包问题进行类的封装； 能对任意给定的 n 种物品的重量、价值及背包限重，输出以上表格 （ 或纵向输出 ）

　； 输出背包问题的解； 本题要求采用 STL 库中的排序算法数据进行排序。

　二、 所用仪器、设备 计算机、 Visual C+ 嗽件。

　三、 实验原理 贪心算法解决背包冋题有几种策略：

　（ 1 ）

　一种贪心准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利 用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的 物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑 n=2, w=[100,10,10], p =[20,15,15], c = 105 当利用价值贪婪准则时，获得的解为 x= [ 1 , 0,0 ，这种方案的总价 值为 2 0 。而最优解为 [0 , 1 , 1 ], 其总价值为 3 0 。

　（ 2 ）

　另一种方案是重量贪心准则是：从剩下的物品中选择可装入背包的重量最小的 物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最 优解。考虑 n= 2 ,w=[10,20], p=[5,100], c= 2 5 。当利用重量贪婪策略时，获得的解为 x =[1,0], 比最优解 [0,1 要差。

　（ 3 ）

　还有一种贪心准则，就是我们教材上提到的，认为，每一项计算 yi=vi/si, 即该 项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次 类推，尽可能的多放，直到装满背包。

　四、 实验方法与步骤

　首先计算每种物品单位重量的价值 Vi/Wi ，然后依贪心选择策略，将尽可能多的单 位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量 未超出 C ,则选择单位重量价值次高的物品，并尽可能多的装入背包。依此策略一直进 行下去，直到背包装满为止。

　采用贪婪准则：每次选择 P/W 最大的物品放入背包。

　注意在这之前的计算每种物品单位重量的价值 Vi/Wi 后，进行排序。

　五、实验结果与数据处理 实验截图：

　E "D:\Program Files\VC+ +6,0\MSDev98\BinV< 一

　请输入背包容积； 7

　选中物品的编号利重盘分别为: 1.06 2.06 2.00 3.0Q 4.00 2.00 总价值为 ：

　1 2 . SOPross any keg to 搜狗拼音输入法全：

　主要代码如下：

　#in elude <stdio.h> #defi ne M 4 struct no de{ float no;// 编号 float value; float weight; float wweight;//若是最后一个的用量 int flag; }Node[M],temp; float Value,curvalue=O; float Weight,curweight=0; //按性价比排序 void sort() { int i,j; for(i=0;i<M-1;i++) { for(j=i+1;j<M;j++) { if((Node[i].value/(float)Node[i].weight)<Node[j].value/(float)Node[j].weight) { temp=Node[i]; Node[i]=Node[j];Node[j]=temp; }

　}

　}

　}

　// 可切割装载方法 void load2(){ int i;

　for(i=0;i<M;i++){ if((Node[i].weight+curweight)<=Weight) {

　curvalue+=Node[i].value; curweight+=Node[i].weight; Node[i].flag=1; }

　else if((Node[i].weight+curweight)>Weight&&(curweight<Weight)){ float t=Weight-curweight; curvalue+=(Node[i].value)/(Node[i].weight)*t; curweight=Weight; Node[i].flag=2; Node[i].wweight=t; }

　else{ Node[i].flag=0; }

　}

　}

　// 进行结果的输出 void putout(){ int i; printf(" 选中物品的编号和重量分别为：

　"); printf("\n\r"); for(i=0;i<M;i++){ if(Node[i].flag==1){ printf("%.2f",Node[i].no); printf(" "); printf("%.2f",Node[i].weight); printf("\n\r"); }

　else if(Node[i].flag==2){ printf("%.2f",Node[i].no); printf(" "); printf("%.2f",Node[i].wweight); printf("\n\r"); }

　} printf("\n 总价值为 ：％ .2f",curvalue); } int mai n(){ int i; static int p; printf("请输入物品的重量和价值：\n"); for(i=0;i<M;i++){ printf("请输入第%d 个物品的重量和价值",i+1); scan f("%f%f%f",&Node[i]. no,&N ode[i].weight,&N ode[i].value); } printf("\n 请输入背包容积："); sca nf("%f",&Weight); sort(); load2(); putout(); return 0; } ［综合实验 六］（选做 ）

　0-1 背包问题的求解 一、实验内容：

　0-1 背包问题有多种解法，如动态规划方法，回溯方法，分枝限界方法等。对于同一 种问题，请参照教材中的算法，给出相应的程序实现。

　注：

　0/1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是Wi ，其价 值为 v ，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最 大。其中，每种物品只有全部装入背包或不装入背包两种选择。

　、所用算法的基本思想及复杂度分析: 1■动态规划法求解 0/1 背包问题：

　1 ）基本思想: 令V （ i , j ）

　表示在前 i （ 1勻乞n ）

　个物品中能够装入容量为 j （ 1 「乞 C ）

　的背包中的物品 的最大值，则可以得到如下动态函数: V(i,0) =V(0, j) =0 ； V(i -1,j)(HW i ) k max^V(i -1, j),V(i -1, j 按照下述方法来划分阶段：第一阶段，只装入前 1 个物品，确定在各种情况下的背 包能够得到的最大价值；第二阶段，只装入前 2 个物品，确定在各种情况下的背包能够 得到的最大价值；以此类推，直到第 n 个阶段。最后， V（ n ,C ）

　便是在容量为C的背包中 第 页共 页

　华北电力大学实验报告 装入 n 个物品时取得的最大价值。

　2) 代码：

　#include<iostream> #include<algorithm> using namespace std; #define N 100 // 最多可能物体数 struct goods // 物品结构体 {

　int sign; // 物品序号 int w; // 物品重量 int p; // 物品价值 }a[N]; bool m(goods a,goods b) {

　return (a.p/a.w)>(b.p/b.w); }

　int max(int a,int b) { return a<b?b:a; }

　int n,C,bestP=0,cp=0,cw=0; int X[N],cx[N]; int KnapSack2(int n,goods a[],int C,int x[]) {

　int V[N][10*N]; for(int i=0;i<=n;i++) V[i][0]=0; for(int j=0;j<=C;j++) V[0][j]=0; for(i=1;i<=n;i++) for(j=1;j<=C;j++) if(j<a[i-1].w) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p); j=C; // 求装入背包的物品 for (i=n;i>0;i--) {

　if (V[i][j]>V[i-1][j]){ x[i-1]=1; j=j-a[i-1].w; }

　else x[i-1]=0;

　return V[n] [C]; //返回背包取得的最大价值 int main() { goods b[N]; printf("物品种数 n:"); scan f("%d" ， &n); //输入物品种数 printf("背包容量 C:"); scan f("%d",&C); //输入背包容量 for (int i=0;i<n;i++) //输入物品 i 的重量 w 及其价值 v { printf("物品 %d 的重量 w[%d]及其价值 v[%d]: ",i+1,i+1,i+1); sca nf("%d%d",&a[i].w, &a[i].p); b[i]=a[i]; } int sum2=K napSack2( n,a,C,X);〃调用动态规划法求 0/1 背包问题 printf("动态规划法求解 0/1背包问题:\nX=["); for(i=0;i< n;i++) coutv<X[i]vv"";// 输出所求 X[n]矩阵 printf("]装入总价值 %d\n",sum2); for (i=0;i <n ;i++) { a[i]=b[i]; }//恢复 a[N]顺序 } 3 ）运行结果: rr D:\Program Fiies\VC.^ — 物品种数 n ：

　6 習包蓉量 C ：

　30 物品 1 的重 *H[1] 及其价值 u[1] ：

　5 7 吻品瓷的重 &ui[2] 及其"介值 v[2] ：

　8 12 物品 3 的 £1 W [3] 及其价值 u[3] ：

　12 18 物品 4 的重及其价值 u[4] ：

　14 20 物品 5 的重量町 5] 及其价值 u[5] ：

　9 16 物品 E 的重 lw[6] 及其价值 u[6] ：

　19 35 动态规划法求解时 1 背包问题：

　X=[ 0 0 0 © 1 1 ] 装入总价值 51 Press any key to continue^ 搜狗拼音输入法全：

　4 ）复杂度分析 ：

　动态规划法求解 0/1 背包问题的时间复杂度为：T （ n）

　=O（n C ）

　2.回溯法求解 0/1 背包问题：

　1) 基本思想：

　回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数 (bou ndi ng function) 来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。

　这种具有限界函数的深度优先生成法称为回溯法。

　对于有 n 种可选物品的 0/1 背包问题，其解空间由长度为 n 的 0-1 向量组成 ， 可用子 集数表示。

　在搜索解空间树时， 只要其左儿子结点是一个可行结点， 搜索就进入左子树。

　当右子树中有可能包含最优解时就进入右子树搜索。

　2) 代码 : #include<iostream> #include<algorithm> using namespace std; #define N 100 // 最多可能物体数 struct goods // 物品结构体 {

　int sign; // 物品序号 int w; // 物品重量 int p; // 物品价值 }a[N]; bool m(goods a,goods b) {

　return (a.p/a.w)>(b.p/b.w); }

　int max(int a,int b) {

　return a<b?b:a; }

　int n,C,bestP=0,cp=0,cw=0; int X[N],cx[N]; int BackTrack(int i) {

　if(i>n-1){ if(bestP<cp){ for (int k=0;k<n;k++) X[k]=cx[k];// 存储最优路径 bestP=cp; }

　return bestP; }

　if(cw+a[i].w<=C){ // 进入左子树 cw=cw+a[i].w; cp=cp+a[i].p; cx[a[i].sign]=1; // 装入背包 BackTrack(i+1); cw=cw-a[i].w; cp=cp-a[i].p; // 回溯，进入右子树 }

　cx[a[i].sign]=0; // 不装入背包 BackTrack(i+1); return bestP; }

　int KnapSack3(int n,goods a[],int C,int x[])

　{

　for(int i=0;i<n;i++) {

　x[i]=0; a[i].sign=i; }

　sort(a,a+n,m);// 将各物品按单位重量价值降序排列 BackTrack(0); return bestP; }

　int main() {

　goods b[N]; printf(" 物品种数 n: "); scanf("%d",&n); // 输入物品种数 printf(" 背包容量 C: "); scanf("%d",&C); // 输入背包容量 for (int i=0;i<n;i++) // 输入物品 i 的重量 w 及其价值 v {

　printf("物品 %d 的重量 w[%d]及其价值 v[%d]: ",i+1,i+1,i+1); scanf("%d%d",&a[i].w,&a[i].p); b[i]=a[i]; }

　int sum3=KnapSack3(n,a,C,X);〃调用回溯法求 0/1 背包问题 printf(" 回溯法求解 0/1 背包问题 :\nX=[ "); for(i=0;i<n;i++) coutv<X[i]vv" ";// 输出所求 X[n]矩阵 printf("] 装入总价值 %d\n",sum3); for (i=0;i<n;i++) {

　a[i]=b[i]; }//恢复 a[N]顺序 3) 运行结果：

　■ L

　"D:\Program Films"…- 口 物品种数 m & „野包容量 t ：

　3Q 物品 1 的 ££w[1 ] 及其价值 v[1] ：

　12 19 敕）品 2fr J j5.£w[2] 及其 2 5 构乔 3 的蛍量叫 3] 及耳价值训 3] : 14 29 物叩*的 $ n 物品 5 的 <£u[5]fi 其价值 u[S]9 U 物丽 E 的虽區#[匍及具忻值 u[E]i 7 12 回阁眩求解 0C 背包冋题：

　X=[ 0 e 1 1 G 1 J 發入总价值的 Press 已 nq to continue 搜狗拼音醯入法全：

　4 ）复杂度分析: 最不理想的情况下，回溯法求解 0/1 背包问题的时间复杂度为：

　T （ n）=° （ 2 ）

　。由于 其对蛮力法进行优化后的算法，其复杂度一般比蛮力法要小。

　空间复杂度：有 n 个物品，即最多递归 n 层，存储物品信息就是一个一维数组，即 回溯法求解0/1 背包问题的空间复杂度为° （ n ）

　。

　3■分支限界法求解背包问题: 1 ）

　基本思想：

　分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。

　一般情况下, 分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件 的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束 条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

　首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。

　在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下 的最大单位重量价值的物品装满剩余容量的价值和。

　算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点， 则将它加入到子集树和活结点优先队列中。

　当前扩展结点的右儿子结点一定是可行结点， 仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点 时为问题的最优值。

　2 ）

　代码 ：

　#in clude<iostream> #i nclude<algorithm> using n amespace std; #define N 100 //最多可能物体数 struct goods //物品结构体 { int sign; //物品序号 int w; //物品重量 int p; //物品价值

　}a[N]; bool m（goods a,goods b）

　{

　return (a.p/a.w)>(b.p/b.w); }

　int max(int a,int b) {

　return a<b?b:a; }

　int n,C,bestP=0,cp=0,cw=0; int X[N],cx[N]; struct KNAPNODE //状态结构体 {

　bool s1[N]; // 当前放入物体 int k; //搜索深度 int b; // 价值上界 int w; // 物体重量 int p; // 物体价值 }; struct HEAP // 堆元素结构体 {

　KNAPNODE *p;〃结点数据 int b; // 所指结点的上界 }; // 交换两个堆元素 void swap(HEAP &a, HEAP &b) {

　HEAP temp = a; a = b; b = temp; }

　// 堆中元素上移 void mov_up(HEAP H[], int i) {

　bool done = false; if(i!=1){ while(!done && i!=1){ if(H[i].b>H[i/2].b){ swap(H[i], H[i/2]); }else{ done = true; }

　i = i/2; }

　}

　}

　// 堆中元素下移 void mov_down(HEAP H[], int n, int i) {

　bool done = false; if((2*i)<=n){ while(!done && ((i = 2*i) <= n)){ if(i+1<=n && H[i+1].b > H[i].b){ i++;

　} if(H[i/2].b<H[i].b){ swap(H[i/2], H[i]); }else{ done = true; }

　}

　}

　}

　// 往堆中插入结点 void insert(HEAP H[], HEAP x, int &n) {

　n++; H[n] = x; mov_up(H,n); }

　// 删除堆中结点 void del(HEAP H[], int &n, int i) {

　HEAP x, y; x = H[i]; y = H[n]; n --; if(i<=n){ H[i] = y; if(y.b>=x.b){ mov_up(H,i); }else{ mov_down(H, n, i); }

　}

　}

　// 获得堆顶元素并删除 HEAP del_top(HEAP H[], int &n) {

　HEAP x = H[1]; del(H, n, 1); return x;

　// 计算分支节点的上界 void bound( KNAPNODE* node, int M, goods a[], int n) {

　int i = node->k; float w = node->w; float p = node->p; if(node->w>M){ // 物体重量超过背包载重量 node->b = 0; // 上界置为 0 }else{ while((w+a[i].w<=M)&&(i<n)){ w += a[i].w; // 计算背包已装入载重 p += a[i++].p; // 计算背包已装入价值 } if(i<n){ node->b = p + (M - w)*a[i].p/a[i].w; }else{ node -> b = p; }

　}

　} // 用分支限界法实现 0/1 背包问题 int KnapSack4(int n,goods a[],int C, int X[]) {

　int i, k = 0; // 堆中元素个数的计数器初始化为 0 int v; KNAPNODE *xnode, *ynode, *znode; HEAP x, y, z, *heap; heap = new HEAP[n*n]; for( i=0; i<n; i++){ a[i].sign=i; } sort(a,a+n,m); xnode = new KNAPNODE; for( i=0; i<n; i++){ xnode->s1[i] = false; }

　xnode->k = xnode->w = xnode->p = 0; while(xnode->k<n) { ynode = new KNAPNODE; *ynode = *xnode; ynode->s1[ynode->k] = true; ynode->w += a[ynode->k].w; ynode->p += a[ynode->k].p; ynode->k ++; bound(ynode, C, a, n); // y.b = ynode->b; y.p = ynode; insert(heap, y, k); // 结点 y 按上界的值插入堆中 znode = new KNAPNODE; // 建立结点 z *znode = *xnode; // 结点 x 的数据复制到结点 z znode->k++; // 搜索深度 ++ bound(znode, C, a, n); // 计算节点 z 的上界 z.b = znode->b; z.p = znode; insert(heap, z, k); // 结点 z 按上界的值插入堆中 delete xnode; x = del_top(heap, k); // 获得堆顶元素作为新的父亲结点 xnode = x.p; }

　v = xnode->p; for( i=0; i<n; i++){ // 取装入背包中物体在排序前的序号 if(xnode->s1[i]){ X[a[i].sign] =1 ; }else{ X[a[i].sign] = 0; }

　}

　delete xnode; delete heap; return v; // 返回背包中物体的价值 }

　void main() {

　goods b[N]; printf(" 物品种数 n: ");

　scanf("%d",&n); // 输入物品种数 printf(" 背包容量 C: "); scanf("%d",&C); // 输入背包容量 for (int i=0;i<n;i++) //输入物品 i 的重量 w 及其价值 v {

　printf("物品 %d 的重量 w[%d]及其价值 v[%d]: ",i+1,i+1,i+1); scanf("%d%d",&a[i].w,&a[i].p); b[i]=a[i]; }

　int sum4=KnapSack4( n,a,C,X);〃调用分支限界法求 0/1 背包问题 printf(" 分支限界法求解 0/1 背包问题 :\nX=[ "); for(i=0;i<n;i++) coutv<X[i]vv" ";// 输出所求 X[n]矩阵 printf("] 装入总价值 %d\n",sum4);

　 4）

　复杂度分析 分支限界法求解 0/1 背包问题的时间复杂度为：

　T （ nr °（ 才 ）

　六、实验心得 此次做完了 5 个算法实验， C++ 编程能力得到了一定的提高，指针的使用，进一步熟 练，而且充分体会到 C++ 指针的灵活带来的便利是其他编程语言无可比拟的。

　在分治策略归并排序时，深入了解了分治策略的使用及归并排序的基本原理，知道 它是怎么实现排序的，并通过编程实现了归并排序。也第一次运用了库函数，学到了很 多知识。在此次编程中，第一次使用了 vector 向量及 array 数组，它们的优势在于动态 添加元素，并且具有栈的一系列操作，十分方便。

　优先队列的使用，使得排序更加简便， 不足：这些代码只是要求功能的实现，并且封装成了类，原先封装类的目的是想生 成动态链接库，通过 c# 简单的图形界面编辑，调用 DLL 中函数，进行显示，以避开复杂 的 C++ 图形用户界面显示，但过程中也出现很多问题，且网上很难找到适合像我这样初 学者看的类似生成动态库代码，无奈使用控制台实现，主要原因还是平时练习的比较少， 很遗憾只编成了 dos 界面的，不过，作为一名计算机专业学生以后我会继续努力，勤加 练习基本功，学好 C 语言，学好算法。