信息学奥林匹克竞赛指导之基础算法—贪心算法

信息学奥林匹克竞赛指导 基础算法—贪心算法 1 -贪心算法 目录 总述 贪心算法的概念及其特点 引例 贪心算法的经典实例 贪心算法的经典应用 贪心算法的练习 2 -贪心算法 总述 近年来的信息学奥赛试题，经常出现求一个问题的可行解或最优解的题目。这类题目是我们所说的最优化问题。贪心算法是求解这类问题的一种常用算法。在众多的算法中，贪心算法可以算得上是最接近人们日常思维的一种算法，常备信息学奥赛选手用于求解一些数据规模很大的问题。 贪心算法一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最优的解。也就是说，贪心算法不从整体最优考虑，它所做出的选择只是局部最优解。 3 -贪心算法 贪心算法的概念及其特点 贪心算法是从问题的初始状态出发，通过若干次的贪心选择而得到的最优值的一种求解问题的策略。 特点： 贪心选择：所谓贪心选择是指应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择，且这种选择只依赖于已作出的选择，不依赖于未作出的选择。 最优子结构：执行算法时，每一次得到的结果虽然都是当前问题的最优解（即局部最优解），但只有满足全局最优解包含局部最优解时，才能保证最终得到的结果是最优解。 4 -贪心算法 引例-1 在N行M列的正整数矩阵中，要求从每行中选出一个数，使得选出的N个数的和最大。 策略：选N次，每一次选出相应行中的最大值即可。 5 -贪心算法 引例-2 在一个N×M的方格中，每一格子赋予一个数（即权值），规定每次移动只能向上或向右。现找出一条路径，使其从左下角至右上角所经过的权值之和最大。 以2×3的矩阵为例： 贪心算法：路径为1→3→4→6 最优解：路径为1→2→10→6 3 4 6 1 2 10 6 -贪心算法 贪心算法的经典实例 最优装载问题 问题描述：给n个物体，第i个物体重量为，选择尽量多的物体，使得总重量不超过C。 思路点拨：由于只关心物体的数量，所以装重的没有装轻的划算。只需要所有物体按重量从小到大排序，一次选择每个物体，直到装不下为止。 部分背包问题 问题描述：有n个物体，第i个物体的重量为，价值为，在总重量不超过C的情况下让总价值最高。每一个物体可以只取走一部分，价值和重量按比例计算。 7 -贪心算法 贪心算法的经典实例 思路点拨：本问题是在上一个问题的基础上增加了价值项，所以不能简单地向上一题那样先选出轻的（轻的可能其价值也小），也不能先拿价值大的（它可能特别重），而应该综合考虑两个因素。一种直观的贪心策略是：优先选出价值与重量的比值最大的，直到重量和正好为C。 注意：由于每个物体可以只选出一部分，因此一定可以让重量恰好为C（或者所有物体全选，总重量还不足C），而且除了最后一个外，所有的物体要么不选，要么全选。 乘船问题 问题描述：有n个人，第i个人的重量为。每艘船的载重量均为C，最多可乘两个人。求用最少的船载所有人的方案。 8 -贪心算法 贪心算法的经典实例 思路点拨：考虑最轻的人i，他应该和谁一起乘呢？如果每个人都不能和他一起乘，则只能每人乘一艘船。否则他应该选择能和他一起乘的人中最重的一个人j。这样的选择只是让“眼前”的浪费最少，因此它是一种贪心策略。 证明： 情况1：i不和任何一个人同乘一艘船，那么可以把j拉过来和他一起乘，总船数不会增加（且可能会减少！），符合贪心策略。 情况2：i和另外一个人k同乘一艘船，其中k比j轻。把j和k交换后，j原来所在的船坦然不会超重（因为k比j轻），因此i与j同乘一艘船，所得到的新解不会更差，符合贪心策略。 9 -贪心算法 贪心算法的经典应用-1 选择不相交区间问题 问题描述：给定n个开区间，选择尽量多个区间，使得这些区间两两没有公共点。 思路点拨：首先按照的顺序排序，一次烤炉个个区间，如果没有和已选择的区间冲突，就选；否则，就不选。 10 -贪心算法 贪心算法的经典应用-1 例题1： 【问题描述】设有n个活动的集合，其中每个活动都要求使用同一资源，如演唱会唱等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间和一个结束时间，且。如果选择了活动i，则它在时间区间内占用资源。若区间与区间不相交，则称活动i和活动j是相容的。也就是说，当或时，活动i与活动j相容。选择出由互相兼容的活动组成的最大集合。 11 -贪心算法 贪心算法的经典应用-1 【输入格式】第一行一个整数n（n<=1000）;接下来的n行，每行两个整数和。 【输出格式】输出尽可能多的互相兼容的活动个数。 【样例输入】 4 1 3 4 6 2 5 1 7 12 -贪心算法 贪心算法的经典应用-1 【样例输出】 2 【数据规模】对于100%的数