实验三贪心算法
实验目的
1. 掌握贪心法的基本思想方法；
2. 了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法；
3. 掌握贪心算法复杂性分析方法分析问题复杂性。
预习与实验要求
1. 预习实验指导书及教材的有关内容，掌握贪心法的基本思想；
2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；
3. 认真听讲，服从安排，独立思考并完成实验。
实验设备与器材
硬件：PC机
软件：C++或Java等编程环境
实验原理
有一类问题是要从所有的允许解中求出最优解，其策略之一是“贪心法”，即逐次实施“贪心选择”：在每个选择步骤上做出的选择都是当前状态下最优的。贪心选择依赖于在此之前所做出的选择，但不依赖于后续步骤所需要的选择，即不依赖于后续待求解子问题。显然，这种选择方法是局部最优的，但不是从问题求解的整体考虑进行选择，因此不能保证最后所得一定是最优解。贪心法是求解问题的一种有效方法，所得到的结果如果不是最优的，通常也是近似最优的。
实验内容
以下几个问题选做一项：
1. 用贪心法实现带有期限作业排序的快速算法
应用贪心设计策略来解决操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题。
假定只能在一台机器上处理N个作业，每个作业均可在单位时间内完成；又假定每个作业i都有一个截止期限di>0（它是整数），当且仅当作业i在它的期限截止以前被完成时，则获得pi的效益。
这个问题的一个可行解是这N个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成。可行解的效益值是J中这些作业的效益之和，即Σp。具有最大效益值的可行解就是最优解。
2. 实现K元归并树贪心算法
两个分别包含n个和m个记录的已分类文件可以在O（n+m）时间内归并在一起而得到一个分类文件。当要把两个以上的已分类文件归并在一起时，可以通过成对地重复归并已分类的文件来完成。例如：假定
X1,X2,X3,X4是要归并的文件，则可以首先把X1和X2归并成文件Y1，然后将Y1和X3归并成Y2，最后将Y2和X4归并，从而得到想要的分类文件；也可以先把X1和X2归并成Y1，然后将X3和X4归并成Y2，最后归并Y1和Y2而得到想要的分类文件。给出n个文件，则有许多种把这些文件成对地归并成一个单一分类文件的方法。不同的配对法要求不同的计算时间。
问题是确定一个把n个已分类文件归并在一起的最优方法（即需要最少比较的方法）
像刚才所描述的归并模式称为二路归并模式（每一个归并步包含两个文件的归并）。二路归并模式可以用二元归并树来表示。叶结点被画成方块形，表示已知的文件。这些叶结点称为外部结点。剩下的结点被画成圆圈，称为内部结点。每个内部结点恰好有两个儿子，表示把它的两个儿子所表示的文件归并而得到的文件。每个结点中的数字都是那个结点所表示的文件的长度（记录数）。一个i级结点在距离根为i-1的地方，在i级结点上的文件的记录都要移动i-1次。如果di是由根到代表文件Fi的外部结点的距离，qi是Fi的长度，则这颗二元归并树的记录移动总量是。这个和数叫做这颗树的带权外部路径长度。一个最优二路归并模式与一颗具有最小权外部路径的二元树相对应。
生成归并树的贪心方法也适用于K路归并的情况。相应的归并树是一颗K元树。所有的内部结点的度数必须为K，所以对于n的某些值，就不与K元归并树相对应。例如：当K=3时，就不存在具有n=2个外部结点的K元归并树。所以有必要引进一定量的“虚”外部结点。每一个虚外部结点被赋以0值的qi。这个虚值不会影响所产生的K元树的带权外部路径长度。
3. 实现背包问题的贪心算法
4. 用贪心算法实现单源最短路径问题
要求：
（1）选择合适的数据结构来表示问题中的变量和结果；
（2）根据贪心算法的基本原理，写出求解问题的伪码算法；
（3）编制C++或JAVA等高级语言程序实现伪码算法；
（4）上机运行程序，验证算法的正确性。
实验报告
1. 描述贪心算法的基本原理；
2. 写出用贪心算法实现问题的伪码算法，写出算法所用到的主
要数据结构；
3. 得出结果，并写出算法的时间复杂性和空间复杂性。
4. 详细填写完成实验的收获和得失，实验过程中遇到的问题、
解决的办法、实验心得以及对该实验的建议和意见。
