2022/12/7本章教学要求及重点难点n 理解贪心方法的基本思想n 掌握背包问题的求解方法n 掌握带有限期的作业排序的基本方法n 掌握用贪心方法求解单源点最短路径的基本方法。 n 重点：用贪心方法求背包问题及带有限期作业排序； n 难点：用贪心方法求单源点最短路径。 2022/12/74.1 一般方法1. 问题的一般特征 问题有n个输入，问题的解是由这n个输入的某个子集组成，这个子集必须满足某些事先给定的条件。n 约束条件：子集必须满足的条件；n 可行解：满足约束条件的子集；可行解可能不唯一；n 目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出；n 最优解：能够使目标函数取极值（极大或极小）的可行解。 分类：根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。 最优化问题求解 贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问题方便地求解。2022/12/7例找零钱 一个小孩买了价值少于1元的糖，并将1元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为25分、10分、5
