下载文档原格式
《算法设计与分析》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。
上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。
手编程序应书写整齐，并经人工检查无误后才能上机。
（2）、上机输入和调试自己所编的程序。
一人一组，独立上机调试，上机时出现的问题，最好独立解决。
（3）、上机结束后，整理出实验报告。
实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。
本书共分阶段4个实验，每个实验有基本题和提高题。
基本题必须完成，提高题根据自己实际情况进行取舍。
题目不限定如下题目，可根据自己兴趣爱好做一些与实验内容相关的其他题目，如动态规划法中的图象压缩，回溯法中的人机对弈等。
其具体要求和步骤如下：实验一分治与递归（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。
三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。
四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。
一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
三、实验提示void chessBoard(int tr, int tc, int dr, int dc, int size) {if (size == 1) return;int t = tile++, // L型骨牌号s = size/2; // 分割棋盘// 覆盖左上角子棋盘if (dr < tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖右下角board[tr + s - 1][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);}// 覆盖右上角子棋盘if (dr < tr + s && dc >= tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖左下角board[tr + s - 1][tc + s] = t;// 覆盖其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);}// 覆盖左下角子棋盘if (dr >= tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr+s, tc, dr, dc, s);else {// 用t 号L型骨牌覆盖右上角board[tr + s][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr+s, tc, tr+s, tc+s-1, s);}// 覆盖右下角子棋盘if (dr >= tr + s && dc >= tc + s)// 特殊方格在此棋盘中chessBoard(tr+s, tc+s, dr, dc, s);else {// 用t 号L型骨牌覆盖左上角board[tr + s][tc + s] = t;// 覆盖其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);}}一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1]是一个已排好序的数组。
《算法设计与分析》实验指导书目录实验一单链表的建立插入及删除 (3)实验二多项式加法 (5)实验三集合的表示与操作算法设计 (7)实验四迷宫问题求解 (8)实验五树的建立及遍历 (11)实验六图的遍历的演示 (12)实验七哈希表的设计 (15)实验八Kruskal算法的设计 (17)实验九归并排序的分治策略设计 (19)实验十哈夫曼编码的贪心算法设计 (21)实验十一递归与迭代程序设计 (22)实验十二多段图问题的动态规划算法设计 (24)实验十三作业调度问题 (26)实验十四回溯算法设计 (28)实验十五搜索顺序的选择 (29)实验十六蛇和梯子 (31)实验十七游戏中寻址算法的设计 (34)实验十八旅行商问题 (36)实验十九骑士游历算法设计 (38)实验二十输油管道问题的设计与实现 (40)实验二十一邮局选址问题的设计与实现 (42)实验二十二会场安排问题的设计与实现 (44)实验二十三目录树打印程序的设计 (46)实验二十四最少演员问题 (48)附：实验（设计）报告参考格式 (50)实验一单链表的建立插入及删除[实验目的]1．掌握单链表的建立插入及删除的算法；2．进一步熟悉指针的用法；[预习要求]1.认真阅读教材或参考书, 掌握线性表算法的基本思想；2.写出求解本实验的程序；3.设计好相应的测试用例。
[类型定义]typedef struct Lnode{int data;struct Lnode *next;}Lnode,*linklist;[实验提示]void create(link *h,int n){//创建单链表link p,q;int i;p=(link)malloc(sizeof(node));p->next=null;*h=p;q=p;for(i=1;i<=n;++i){p=(link)malloc(sizeof(node));scanf("%d",&p->data);p->next=null;q->next=p;q=p;}}void print(link h){//输出单链表link p;p=h->next;while(p){printf("%d ",p->data);p=p->next;}}void insertlist(linklist *L,int i,int e){//在单链表的第i个元素之前插入元素值为e的结点}void dellist(linklist *L,int i,int *e){//删除单链表的第i个结点，被删结点通过 e返回}[实验步骤]1.先用插表头或插表尾的方法建立单链表并输出，并测试你的程序，直至正确为止；2.再进行插入和删除程序的设计；3.将你的程序和实录的界面存盘备用。
算法设计与分析实验指导书. . .. . .算法设计与分析实验指导书东北大学软件学院2012年.. .专业. .目录算法设计与分析 (1)实验指导书 (1)前言 (3)实验要求 (4)实验1 分治法的应用（2学时） (5)1.实验目的 (5)2.实验类型 (5)3.预习要求 (5)4.实验基本要求 (5)5.实验基本步骤 (7)实验2动态规划（2学时） (9)1.实验目的 (9)2.实验类型 (9)3.预习要求 (9)4.实验基本要求 (9)5.实验基本步骤 (10)实验3 回溯法（4学时） (12)1.实验目的 (12)2.实验类型 (12)3.预习要求 (12)4.实验基本要求 (12)5.实验基本步骤 (13)前言《算法设计与分析》是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。
通过对计算机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定基础。
要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及其分析方法。
能将这些方法灵活的应用到相应的问题中，并且能够用C++实现所涉及的算法，并尽量做到低复杂度，高效率。
通过本课程的实验，使学生加深对课程容的理解，培养学生严密的思维能力，运用所学知识结合具体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热情。
希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。
希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使《算法设计与分析》课程成为对大家有益的课程。
实验要求《算法设计与分析》课程实验的目的是为了使学生在课堂学习的同时，通过一系列的实验，使学生加深理解和更好地掌握《算法设计与分析》课程教学大纲要求的容。
在《算法设计与分析》的课程实验过程中，要求学生做到：（1）仔细观察调试程序过程中出现的各种问题，记录主要问题，做出必要说明和分析。
计算机科学与技术学院算法分析与设计实验指导书2011年8月于洪编写2015年9月周应华修订目录实验一分治策略排序 (3)实验二减治策略查找顺序表 (5)实验三动态规划求解0/1背包问题 (8)实验四贪心算法求解最短路径问题 (10)附录1 关于文件的操作 (12)附录2 关于如何统计运算时间 (13)实验一分治策略排序实验目的1）以排序问题为例，掌握分治法的基本设计策略；2）熟练掌握合并排序算法的实现；3）熟练掌握快速排序算法的实现；4) 理解常见的算法经验分析方法。
实验环境计算机、C语言程序设计环境实验学时2学时实验内容与步骤1.准备实验数据要求：编写一个函数data-generate，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。
这些数作为本算法实验的输入数据。
2.实现合并排序算法要求：实现mergesort算法。
输入：待排数据文件data.txt；输出：有序数据文件resultsMS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeMS。
合并排序算法（类C语言）：/* 数组A[] 中包含待排元素；array B[] is a work array */TopDownMergeSort(A[], B[], n){TopDownSplitMerge(A, 0, n, B);}// iBegin is inclusive; iEnd is exclusive (即：A[iEnd]不是待排元素)TopDownSplitMerge(A[], iBegin, iEnd, B[]){if(iEnd - iBegin < 2) // 如果只有1个待排元素，返回。
return;// recursively split runs into two halves until run size == 1,// then merge themiMiddle = (iEnd + iBegin) / 2; // 划分TopDownSplitMerge(A, iBegin, iMiddle, B);TopDownSplitMerge(A, iMiddle, iEnd, B);TopDownMerge(A, iBegin, iMiddle, iEnd, B); // 合并；元素放到数组B中。
《算法设计与分析》课程实验教学大纲Design and Analysis of Computer Algorithm总学时 16 总学分 0.5 实验学时 16一、基本情况1. 课程性质：专业实践2. 设课方式：独立设课3. 适用专业：计算机科学与技术专业4. 开课学期：第5学期5. 实验教材：《算法设计与分析》实验指导书6. 先修课程：高级语言程序设计、离散数学、数据结构二、课程简介算法设计与分析实验将覆盖计算机软件实现中的大部分算法，具有一定的深度和广度，目的是让学生掌握递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等算法思想；能独立运用相关算法策略来分析、解决实际问题并编程实现。
同时，算法设计与分析实验是对学生在软件设计方面的综合训练，包括问题分析，总体结构设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。
通过理论联系实际，最终提高学生动手操作的能力以及分析问题和解决问题的能力，培养对算法的复杂性进行分析的逻辑思维能力。
三、实验目的与任务实验是教学内容的重要一环，其目的一方面是为了让学生掌握算法设计与分析中的一些常用的典型的算法设计思想和方法；另一方面是为了让学生切实掌握各种算法的具体实现方法，培养学生的实际动手能力，加强学生创新思维能力的培养。
四、课程的基本要求（1）了解实验目的，熟悉实验环境。
（2）预习实验，准备好实验题目和操作步骤。
（3）能编译调试源程序,分析错误原因并加以修改,得出正确结果。
（4）能运用所学的知识正确分析程序得出的结果，并能给出改进的方案。
（5）将上述各项要求及实验结果编写成实验报告。
实验前学生要认真预习实验内容，按要求编写源程序及准备测试数据。
实验中,要按操作规程操作计算机，集中精力调试程序,并认真测试实验数据。
对实验程序的故障应自行分析解决，不拷贝其它人的成果。
对实验得出的结果能加以分析，提出改进的具体措施。
掌握递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等算法思想；能独立运用相关算法策略分析问题、解决实际问题并编程实现。
实验一串匹配程序设计（2学时）一、实验目的(1). 熟练掌握串匹配的含义(2). 掌握BF算法匹配的过程并编程实现(3). 熟悉C++编译环境的基本操作二、实验内容给定两个字符串S和T，用BF算法，在主串S中查找字串T，输出结果，输出时要求有文字说明。
请编写程序。
三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（匹配成功或不成功）(3)、写出完整的程序四、实验结果实验二排序问题程序设计（2学时）一、实验目的(1). 掌握选择排序和起泡排序的基本思想(2). 掌握两种排序方法的具体实现过程(3). 在掌握的基础上编程实现两种排序方法二、实验内容输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明。
请编写程序。
三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（序列本身已是有序序列，序列不是有序序列）(3)、写出完整程序四、实验结果实验三数字旋转方阵程序设计（2学时）一、实验目的(1). 掌握分治法的设计思想(2). 掌握数字旋转方阵的具体实现过程(3). 熟练掌握二维数组的使用方法(4). 在掌握的基础上编程实现数字旋转方阵的实现过程二、实验内容给出一个初始数据，在此数据的基础上由外层向里层填写数据，完成一个数字旋转方阵，输出结果，输出时要求有文字说明。
请编写程序。
三、实验要求(1)、熟悉C++编译环境的基本操作(2)、考虑各种可能的情况（方阵有一层，两层或更多层）(3)、写出完整程序四、实验结果实验四排序中分治法的程序设计（2学时）一、实验目的(1). 掌握归并排序和快速排序的划分方法(2). 掌握归并排序和快速排序的具体分治策略(3). 在掌握的基础上编程两种排序方法的实现过程二、实验内容给出一个初始序列，分别用归并排序和快速排序两种分治法将所给序列变换为有序序列，输出结果，输出时要求有文字说明。
《算法设计与分析》课程实验指南(适合于非计算机科学与技术专业)实验项目1 串匹配问题1．实验题目给定一个文本，在该文本中查找并定位任意给定字符串。
2.学时安排2个学时。
3.实验目的(1)深刻理解并掌握蛮力法的设计思想；(2)提高应用蛮力法设计的技能；(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。
4.实验要求(1)实现BF算法；(2)实现BF算法的改进算法：KMP算法；(3)对上述2个算法进行时间复杂性分析，并设计实验程序验证分析结果。
实验项目2 最近对问题1.实验题目设p1=(x1,y1)，p2=(x2,y2)，…，pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近点对。
2.学时安排2个学时。
3.实验目的(1)进一步掌握递归算法的设计思想以及递归程序的调试技术；(2)理解这样一个观点：分治与递归经常同时应用在算法设计之中。
4.实验要求（1）分别用蛮力法和分治法求解最近对问题；（2）分析算法的时间性能，设计实验程序验证分析结论。
实验项目3 八枚硬币问题1.实验题目在8枚外观相同的硬币中，有一枚是人民币假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。
可以通过一架天平来任意比较两组硬币，设计一个高效的算法来测出这枚假币。
2.学时安排2个学时。
3.实验目的(1)深刻理解并掌握减治法的设计思想；(2)提高应用减治设计算法的技能；(3)理解这样一个观点：建立正确的模型对于问题的求解是非常重要的。
4.实验要求(1)设计减治算法实现8枚硬币问题；(2)设计测试数据，写出程序文档。
实验项目4 0/1背包问题1.实验题目给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品(物品不可分割)，使得装入背包中物品总价值最大。
2.学时安排2个学时。
《算法分析与设计》实验指导与报告书实验目录实验1 求最大公约数 (1)实验2 斐波那契数列 (3)实验3 最近对问题 (6)实验4 堆排序 (7)实验5 霍纳法则和二进制幂 (8)实验6 字符串匹配问题 (9)实验7 Warshall算法和Floyd算法 (10)实验8 最优二叉查找树 (11)实验9 Huffman编码* (12)实验10 求解非线性方程* (13)实验11 投资问题* (14)注：（1）实验4和实验5为变治法应用，二选一；（2）实验7和实验8为动态规划法应用，二选一；（3）带*号的实验为选做实验，根据课时及学生实验完成情况机动安排。
实验1 求最大公约数{c = a;a = b;b = c;}while(a % b != 0){c = a % b;a = b;b = c;}printf("%d", b);return 0;}连续整数检测算法最大公约数算法：#include <stdio.h>int main(){int a,b,t;printf("Please input two integers: ");scanf("%d %d",&a,&b);if(a<b)t=a;elset=b;while(t>=1){if((a%t==0)&&(b%t==0))break;t--;}printf("%d",t);return 0;}相减循环：#include<stdio.h>int main(){int m,n;printf("Please input two integers: ");scanf("%d%d",&m,&n);while(m!=n)if(m>n) m=m-n;else n=n-m;printf("%d",m);return 0;}教师评分实验2 斐波那契数列实验目的（1）求斐波那契数列；（2）区分递归和递推思想。
《算法分析与设计》实验指导.实验一锦标赛问题[实验目的]1.基本掌握分治算法的原理.2.掌握递归算法及递归程序的设计.3.能用程序设计语言求解锦标赛等问题的算法.[预习要求]1.认真阅读数据结构教材和算法设计教材,了解分治算法原理;2.设计用分治算法求解背包问题的数据结构与程序代码.[实验题]【问题描述】设有n=2k个运动员要进行网球循环赛。
现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能参赛一次；（3）循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。
在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。
其中1≤i≤n，1≤j≤n-1。
[实验提示]我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。
递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
这时只要让这两个选手进行比赛就可以了。
1 2 3 4 5 6 71 2 3 4 5 6 7 82 1 43 6 7 8 53 4 1 2 7 8 5 61 2 3 4 3 2 1 8 5 6 71 2 3 4 5 6 7 8 1 4 3 21 2 1 4 3 6 5 8 7 2 1 4 31 2 3 4 1 2 7 8 5 6 3 2 1 42 1 43 2 1 8 7 6 54 3 2 1（1）（2）（3）图1 2个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。
其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。
据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。
依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
《算法设计与分析》实验指导书《算法设计与分析》实验指导书本文档主要用于《算法设计与分析》课程的实验指导。
《算法设计与分析》旨在教会学生处理各种问题的方法，通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。
通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识，培养学生的实际动手能力，加强学生创新思维能力的培养。
本课程设计了7个设计型实验。
实验内容包括用分治法、动态规划、贪心法、回溯法以及分支限界法求解问题。
一、实验内容安排二、实验基本要求实验前要求学生一定要先了解实验目的、内容、要求以及注意事项，要求学生熟悉实验对象，设计并编写相应的算法。
学生应独立完成所布置实验内容，编写代码，运行程序，记录结果并撰写实验报告。
三、实验报告要求实验结束后，应及时整理出实验报告，实验报告提交书面文档。
四、考核方式理论考试（60％）＋实验（30％）+作业（10%）五、实验内容与指导实验一快速排序问题1．实验目的(1) 用分治法求解该问题。
2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。
3．实验内容有n个无序的数值数据，现要求将其排列成一个有序的序列。
4. 实验步骤(1) 输入实现该问题的源代码；(2) 输入测试数据，验证代码的正确性。
5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。
(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验二最少硬币问题1．实验目的(1) 用动态规划求解该问题。
2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。
3．实验内容有n种不同面值的硬币，各硬币面值存于数组T[1:n]；现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。
对于给定的1≤n≤10，硬币面值数组、各面值的个数及钱数m，0<=m<=2001，设计一个算法，计算找钱m的最少硬币数。
《算法分析与设计》实验指导.实验一锦标赛问题[实验目的]1.基本掌握分治算法的原理.2.能用程序设计语言求解锦标赛等问题的算法;[预习要求]1.认真阅读数据结构教材和算法设计教材,了解分治算法原理;2.设计用分治算法求解背包问题的数据结构与程序代码.[实验题]【问题描述】设有n=2k个运动员要进行网球循环赛。
现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能参赛一次；（3）循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。
在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。
其中1≤i≤n，1≤j≤n-1。
[实验提示]我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。
递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
这时只要让这两个选手进行比赛就可以了。
1 2 3 4 5 6 71（1）（2）（3）图1 2个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。
其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。
据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。
依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
[实验步骤]1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;2.应用设计的算法和程序求锦标赛问题;3.去掉测试程序,将你的程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.阐述分治算法原理;3.提交实验程序的功能模块;4.记录最终测试数据和测试结果。
[思考与练习]【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。
假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。
实验二背包问题[实验目的]3.能用程序设计语言实现求解背包问题的算法;4.基本掌握动态规划法（贪心）的原理方法.[预习要求]3.认真阅读数据结构教材和算法设计教材,了解背包问题的常用算法原理;4.设计用动态规划算法求解背包问题的数据结构和递归程序.[实验题]【背包问题】有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量W，但选中物品的价值之和最大。
[实验提示]设n件物品的重量分别为w0、w1、…、w n-1，物品的价值分别为v0、v1、…、v n-1。
采用递归寻找物品的选择方案。
设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组option[ ]，该方案的总价值存于变量maxv。
当前正在考察新方案，其物品选择情况保存于数组cop[ ]。
假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品；当前方案已包含的物品的重量之和为tw；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值为tv。
算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。
因为当方案的总价值不比maxv大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。
对于第i件物品的选择考虑有两种可能：（1）考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。
选中后，继续递归去考虑其余物品的选择。
（2）考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。
按以上思想写出递归算法如下：try(物品i，当前选择已达到的重量和，本方案可能达到的总价值tv){ /*考虑物品i包含在当前方案中的可能性*/if(包含物品i是可以接受的){ 将物品i包含在当前方案中；if (i<n-1)try(i+1,tw+物品i的重量,tv);else/*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存;恢复物品i不包含状态；}/*考虑物品i 不包含在当前方案中的可能性*/ if (不包含物品i 仅是可男考虑的) if (i<n-1)try(i+1,tw,tv-物品i 的价值)； else/*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存;}并设限制重量为7。
则按以上算法，下图表示找解过程。
由图知，一旦找到一个解，算法就进一步找更好的佳。
如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找，而是立即终止该分支，并去考察下一个分支。
[实验步骤]4.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 5. 应用设计的算法和程序求解背包问题;6. 去掉测试程序,将你的程序整理成功能模块存盘备用.[实验报告要求]5.阐述实验目的和实验内容;6.阐述求解背包问题的算法原理;7.提交实验程序的功能模块;8.记录最终测试数据和测试结果。
[思考与练习]请用其它的算法（如贪心、分支限界等）求解背包问题。
实验三作业调度问题[实验目的]1.熟悉多机调度问题的算法；2.进一步掌握贪心算法3.提高分析与解决问题的能力。
[预习要求]1.认真阅读教材或参考书, 掌握贪心算法的基本思想；2.写出求解“作业调度”的程序；3.设计好测试用例。
[实验题]要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。
作业不能拆分成更小的子作业。
[实验提示]1.把作业按加工所用的时间从大到小排序；2.如果作业数目比机器的数目少或相等，则直接把作业分配下去；3 .如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。
typedef struct Job{int ID;//作业号int time;//作业所花费的时间}Job;typedef struct JobNode //作业链表的节点{int ID;int time;JobNode *next;}JobNode,*pJobNode;typedef struct Header //链表的表头int s;pJobNode next;}Header,pHeader;int SelectMin(Header* M,int m){int k=0;for(int i=1;i<m;i++){if(M[i].s<m[k].s)k=i;}return k;}[实验步骤]1先用贪心算法求解该问题，并测试你的程序，直至正确为止；2针对问题实例，实录运行时的输入、输出文件；3将你的程序和实录的界面存盘备用。
[实验报告要求]阐述实验目的和实验内容；1提交模块化的实验程序源代码；2简述程序的测试过程，提交实录的输入、输出文件；3鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。
实验四回溯算法设计[实验目的]1.掌握回溯法解题的基本思想；2.掌握回溯算法的设计方法；3.针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。
[预习要求]1.认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；2.了解子集和数问题及解向量的定长和变长状态空间表示；3.针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；4.分析深度优先扩展状态空间树节点或回溯的条件；5.分析和设计生成解向量各分量可选值的实现方法；6.设计和编制回溯算法的递归和迭代程序。
[实验题]【组合数】找出从自然数1，2，…，n中任取r个数的所有组合。
[实验提示]回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。
当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。
如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。
在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。
扩大当前候选解的规模，以继续试探的过程称为向前试探。
可以采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：（1）a[i+1]>a[i]，后一个数字比前一个大；（2）a[i]-i<=n-r+1。
按回溯法的思想，找解过程可以叙述如下：首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。
因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为1，2。
继续这一过程，得到候选组合1，2，3。
该候选解满足包括问题规模在内的全部条件，因而是一个解。
在该解的基础上，选下一个候选解，因a[2]上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。
由于对5不能再作调整，就要从a[2]回溯到a[1]，这时，a[1]=2，可以调整为3，并向前试探，得到解1，3，4。
重复上述向前试探和向后回溯，直至要从a[0]再回溯时，说明已经找完问题的全部解。
按上述思想写成程序如下：void comb(int n,int r){ int i,j; i=0; a[i]=1;do { if (a[i]-i<=n-r+1)/*还可以向前试探*/{ if (i==r-1)/*已找到一个组合*/{ for (j=0;j<r;j++) printf(“%4d”,a[j]); printf(“\n”);a[i]++; continue;}i++;a[i] = a[i-1] + 1; /*向前试探*/} else { if (i==0) return;/*已找到所有解*/a[--i]++; } /*回溯*/}while (1);}[实验步骤]1.录入、修改并测试你的程序，直至正确为止；2.针对问题实例，实录运行时的输入、输出界面；3.将你的程序和实录的界面存盘备用。
[实验报告要求]1.阐述实验目的和实验内容；2.提交模块化的实验程序源代码；3.简述程序的测试过程，提交实录的输入、输出界面；4.鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。
