第ｌ３卷 Ｖｏｌ＿１３ 第３期 Ｎｏ．３ 重庆电力高等专科学校学报 Ｊｏｕｒｎａｌ ｏｆ Ｃｈｏｎｇｑｉｎｇ Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ Ｃｏｌｌｅｇｅ ２００８年９月 Ｓｅｐ．２００８
贪心算法的探讨与研究
常友渠 ，肖贵元 ，曾敏
（１．重庆大学计算机学院，重庆４０００４４；２．重庆电力高等专科学校，重庆４０００５３；
３．重庆机电工业学校，重庆４０２１６０）
【摘要】本文讲述了贪心算法的含义，探讨并研究了贪心算法的基本思路及实现过程，通过实例分析了贪心 算法的具体应用、特点及存在的问题。 【关键词】贪心算法；贪心策略；找零问题；背包问题 【中图分类号】ＴＰ３１２ 【文献标识码】Ａ 【文章编号】１００８．８０３２（２００８）０３—００４０—０３
１贪心算法的含义 ２・３
贪心算法是一种能够得到某种度量意义下的
最优解的分级处理方法，它总是做出在当前看来是 最优的选择，也就是说贪心策略并不是从整体上加
以考虑，它所做出的选择只是在某种意义上的局部 最优解算法。
２贪心算法的基本思路及实现算法
的过程
２．１贪心法的基本思路
贪心算法的基本思路是从问题的某一个初始 解出发一步一步地进行，根据某个优化测度，每一
步都要确保能获得局部最优解。每一步只考虑一 个数据，他的选取应该满足局部优化的条件。若下
一个数据和部分最优解连在一起不再是可行解时， 就不把该数据添加到部分解中，直到把所有数据枚 举完，或者不能再添加算法停止。
２．２实现该算法的过程
（１）应用同一规则ｆ，将原问题变为一个相似 的、但规模更小的子问题
（２）从问题的某一初始解出发； Ｗｈｉｌｅ（能朝给定总目标前进一步）
求出可行解的一个解元素； （３）由所有解元素组合成问题的一个可行解；
收稿日期：２００８—０５—２３ 贪心算法的核心
贪心算法的核心问题是选择能产生问题最优 解的最优度量标准，即具体的贪心策略。
３实例分析及其算法的实现
6 算法设计与分析课程教学大纲
【适用专业】 计算机科学与技术
【课 时】 理论课时：32
【学 分】 2
【课程性质、目标和要求】
《算法设计与分析》是计算机科学与技术专业的专业课。无论是计算科学还是计算实践，算法都在其中扮演着重要角色。本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。
课程基本要求是
⑴掌握算法分析的基本概念和理论。
⑵掌握算法设计技术和分析算法以及算法复杂性。
【教学时间安排】
本课程计 2 学分，理论课时32, 学时分配如下：
序号 课程内容/实验名称 实验类型 课时 备注
1 算法引论 理论课时2
2 递归与分治策略/分治法实验 理论课时4
3 动态规划/动态规划实验 理论课时5
4 贪心算法 理论课时3
5 回溯法 理论课时3
6 分支限界法 理论课时3
7 概率算法 理论课时3
8 NP完全性理论 理论课时3
9 近似算法 理论课时3
6 10 算法优化策略 理论课时3
合 计 理论课时32
【教学内容要点】
第一章 算法引论
一、学习目的要求
1．了解算法的计算复杂性分析方法
2．理解算法分析的基本理论
3．掌握算法分析的基本概念
二、主要教学内容
1. 算法的基本概念
2. 表达算法的抽象机制
3. 采用Java语言与自然语言相结合的方式描述算法的方法
4. 算法的计算复杂性分析方法
第二章 递归与分治策略
一、学习目的要求
1．理解典型范例中递归与分治策略应用技巧
2．掌握递归与分治策略
3．掌握数学归纳法证明算法正确性方法
二、主要教学内容
1. 递归的概念
2. 分治法的基本思想
3. 二分搜索技术
板材切割优化算法的实现与比较
第一章 引言
板材切割是制造业中重要的工艺之一，目的是最大限度地利用板材，减少浪费。随着计算机技术的不断发展，利用计算机实现板材切割优化算法已成为当前工业界广泛关注的研究领域之一。板材切割的优化算法旨在找到一种最优的切割方案，以最小化废料数量或最大化使用率。
本文将介绍两种常见的板材切割优化算法，分别是贪心算法和遗传算法，通过实验比较两种算法的性能，并着重讨论如何在实际应用中选择最佳的算法。
第二章 贪心算法
贪心算法是一种简单的启发式算法。它的主要思想是在每一步中选择当前最好的选择，以期望最终结果也是最佳的。在板材切割问题中，贪心算法的具体实现如下：
1.按照板材尺寸排序，从最大的板材开始切割。
2.选择合适的模板尺寸，以覆盖需要切割的板材。
3.尽可能多地剪出这一模板所能承载的片材数量。
4.重复步骤2和3，直至所有板材都被切割完毕。 尽管贪心算法非常简单易懂，但是在实际应用中，它并不总是最优的。由于贪心算法只考虑当前的最优解，而忽视了全局最优解，因此在处理一些复杂的切割情况时可能出现不好的结果。
第三章 遗传算法
遗传算法是一种进化算法，其核心思想是通过模拟自然选择和遗传的过程，寻找最优解。在板材切割问题中，遗传算法的具体实现如下：
1.初始种群的生成：随机生成一组合法的切割方案，作为初始种群。
2.适应度函数的确定：以废料数量或使用率作为适应度函数。
3.选择：按照适应度函数的大小，选择某些个体作为下一代的父母。
4.交叉：通过随机选择两个父母来生成子代，交叉的位置也是随机的。
5.变异：通过随机的方式来改变个体的某个优化参数。
6.新种群的生成：将交叉和变异产生的子代和父代合并生成新的种群。
7.重复步骤3至6，直到达到终止条件。 可以看出，遗传算法能够全面考虑切割问题的多种变量和约束条件，因此，它通常比贪心算法更加优秀。但是，由于遗传算法的实现非常复杂，计算量较大，因此速度相对较慢，不适合处理实时性要求比较高的切割场景。
第3章 贪心算法 贪心算法一般来说是解决“最优问题”，具有编程简单、运行效率高、空间复杂度低等特点。是程序竞赛中的一个有力武器，受到广大同学们的青睐。 贪心算法一般是求“最优解”这类问题的。最优解问题可描述为：有n个输入，它的解是由这n个输入的某个子集组成，并且这个子集必须满足事先给定的条件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。这些可行解可能有多个。为了衡量可行解的优劣，事先给了一个关于可行解的函数，称为目标函数。目标函数最大（或最小）的可行解，称为最优解。 贪心算法的正确性证明虽然不容易，但一些常见的方法还是值得总结的。 1．构造法 根据描述的算法，用贪心的策略，依次构造出一个解，可证明一定是合法的解。即用贪心法找可行解。 2．反证法 用贪心的策略，依次构造出一个解S1。假设最优解S2不同与S1，可以证明是矛盾的。从而S1就是最优解。 3．调整法 用贪心的策略，依次构造出一个解S1。假设最优解S2不同与S1，找出不同之处，在不破坏最优性的前提下，逐步调整S2，最终使其变为S1。从而S1也是最优解。 3.1 构造法 构造法就是从一个空的解开始，根据贪心策略，逐步将新的内容加入原有的解中，直到满足要求或无法将新的元素加入为止。也可以将使用相反的手段，即先将整个解设定为一个最大的集合，然后，用贪心策略逐步从原有解中取出元素，直至满足要求或无法取出元素为止。本节例题将介绍第一种贪心的例子。 3.1.1 〖案例1〗订票 一家票务办公室为音乐会售票。它们以出售某一固定数量的连号票（简称套票）来替代常见的单张票销售。票务办收到了大量的购票订单。套票的订单以该套票中最小的座位号作为标识。然而票务办并不能满足所有的订单，而且如果他们完全按照观众的要求来分·60·
ACM程序设计培训教程
配座位，就会出现很多空位。为此票务办采取了如下的座位分配和价格策略： 如果一个订单被接受且完全按照观众的要求安排座位，那么观众就要付全价(每套票2 petaks)；如果一个订单虽被接受但是至少有一个座位与观众的要求不同，那么顾客只需付半价（每套票1 petaks)。 现在的目标是怎样才能使总收入最高。编写程序计算能够获得的最大收入（子任务A）；并给出实现这一收入所选择的订单和座位分配法（子任务B）。 文件ticket.in的第一行含有两个整数： 座位总数M (1 ≤ M ≤ 30000)和每套票所含的座位数L (1 ≤ L ≤ 100)。座位从1到M编号。 第二行是收到的订单数N (1 ≤ N ≤ 100000)。 第三行包含N个整数，确定了订单的详细信息。这一行的第i个数z (1 ≤ z ≤ M-L+1)，表示第i份订单要求套票座位从z到z+L-1。 文件ticket.out的第一行包含一个整数S，为能够获得的最大收入（子任务A）。 第二行是最后接受的订单数Q。 接下来的Q行表示座位分配方式（子任务B）。每行都有两个整数x y。表示观众x分到的座位从y号开始。注意应按座位号的增序排列这Q行。 如果有多种实现的可能，仅需输出一种即可。 service.in 20 3 7 4 2 10 9 16 15 17 service.out 9 6 4 1 1 4 2 7 3 10 6 13 5 16 ·61· 第3章 贪心算法
