计算基础教程 3

授课内容贪心算法学时2教学目标知识目标理解贪心算法的核心思想与适用场景掌握贪心选择性质和最优子结构的基本含义掌握最优装载、活动选择两类问题的贪心策略了解贪心算法不回溯、局部最优的典型特点能力目标提升多阶段决策问题的规律识别与建模能力强化贪心策略的逻辑分析与算法设计能力培养算法择优选用与实际问题求解能力重点与难点重点贪心算法的核心思想与基本步骤贪心选择性质与最优子结构的理解最优装载问题的贪心策略与实现步骤活动选择问题的贪心策略与实现步骤难点正确判断问题是否适合使用贪心算法为实际问题设计合理有效的贪心策略教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接前面基础算法，进入贪心算法的系统学习贪心算法是竞赛、考级、面试中的高频常用算法贪心思路简洁高效，适合解决多阶段最优决策问题学会贪心思想能显著提升问题分析与算法设计能力本章通过典型实例，快速掌握贪心算法的实用技巧第二部分：新课讲解一、贪心算法概述1、算法思想贪心算法的策略是在每一步选择中，都选择当前看起来最优的选项。这种选择是基于局部最优的判断，而不考虑全局最优解。通过贪心策略，每一步都在当前情况下做出最优的选择，希望最终能够得到全局最优解。2、贪心选择性质贪心选择性质是使用贪心算法的前提之一，它要求必须保证每一步贪心策略所求得的解都是最优解的一部分。贪心选择性质一般使用交换论证法进行证明。3、最优子结构如果一个问题的最优解包含其子问题的最优解，称此问题具有最优子结构性质。这一性质也可以这样理解：问题的最优解可以通过一系列局部最优解的组合来得到。最优子结构一般通过反证法来证明。4、贪心算法的特点着眼当前，简单高效不回溯二、典型例题1、最优装载题目n个集装箱1，2，…，n装上轮船，集装箱i的质量为wi，轮船装载质量限制为C，要求在体积不受限制的情况下，将尽可能多的集装箱装上轮船。【输入格式】输入的第一个整数为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是一个非负整数n（n≤1000）和一个非负整数C（C≤10000），分别表示集装箱的个数以及轮船的载重量。接下来有n行，每行一个非负数，表示每个集装箱的重量。【输出格式】对应每个测试样例输出一行，格式为"DV"。其中，D为轮船可以装载的集装箱数量的最大值，V为满足D最大时轮船的实际载重量。算法这个问题可以使用贪心算法，规则为：每次都挑选剩余集装箱中重量最轻的进行装载即可，此策略下很容易证明具有贪心选择性质和最优子结构。具体步骤为：①对所有集装箱按重量从小到大排序。②每次选择最轻的集装箱装船，然后判断是否超重。③重复上一步，直到超重停止。④处理并输出答案。程序见课本。2、活动选择题目学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。现在给出n个活动使用礼堂的起始时间和结束时间，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。【输入格式】第一行一个整数n(n<=1000)；接下来的n行，每行两个整数，第一个是起始时间，第二个是结束时间。（起始时间<结束时间<=32767）【输出格式】输出最多能安排的活动个数。算法使用贪心算法进行选择，优先安排结束时间早的活动，此策略下很容易证明具有贪心选择性质和最优子结构。假设各活动的时间占用情况如下图所示。第一次选择按“结束时间最早”进行选择，即选择②。注意不能按“开始时间最早”进行选择，那样会选择①。第二次选择在与已选活动不冲突的情况下，按“结束时间最早”进行选择，因此选择③。说明：活动⑥虽然结束时间更早，但与上一个活动冲突而不能选择。后续选择规则同第二次选择。程序见课本。第三