浙江财经大学
信工学院ACM集训队

浅谈贪心算法

本文由 Ocrosoft 于 2016-08-01 12:07:02 发表

PPT下载:本地下载
视频下载:百度网盘

内容导引:

贪心算法的基本思想
贪心算法的基本思路
贪心算法的进行过程
基本题型与例题解析

基本思想:

•在不可预见后面会发生什么的情况下,我们都会选择在当前情况下看起来是最好的选择。这就是贪心算法的基本思想。
•那么贪心算法对于整体来说,不一定作出了最好的决策,只是在一定意义上是局部最优解。不过对许多问题,它作出的局部最优解的组合就是整体最优解。最小生成树的Prim算法和Kruskal算法就是贪心算法的经典应用。
•在某些情况下,我们并不需要最优解,只是需要一个较优解,那么贪心算法执行简单,是很好的选择,在现实中应用广泛。

基本要素:

•一个问题可以贪心,需要有一下两个性质:
•贪心选择性:这个问题的整体最优解可以通过一系列局部最优的选择来达到。在后面有动态规划的内容,贪心与动态规划都是寻找最优解的手段,但是动态规划是从后往前寻找答案,而贪心是从前往后寻找答案,所以贪心相比动态规划有一定的局限性,但由于构造简单,仍是一个重要的算法。
•最优子结构性质:这个问题的最优解包含其子问题的最优解时,这个问题就有最优子结构性质。如果一个问题不拥有最优子结构性质,就不能用贪心与动态规划解决。

基本思路:

      从问题的初始状态开始,往最终状态前进,每次都选择当前最好的选择。当到达最终状态时停止;如果不能再作出选择,又未到达最终状态,那么这个问题不能或利用贪心思想不能到达最终状态,停止。

执行过程:

      用一个背包问题来解释:

      有一个背包,其容量M一定。物品有若干个,要求尽可能让装入背包中的物品的总价值最大,但是不能超过总容量。

      那么贪心思路有一下三个:

•思路1:每次挑选价值最大的物品,直到无法选择物品。
•思路2:每次挑选重量最小的物品,直到无法选择物品。
•思路3:每次选择单位重量价值最大的物品,直到无法选择物品。

思路分析:

1 2 3 4

如何解决背包问题:

•从上面的三种思路来看,该背包问题并不能用贪心解决。
•一般来说,背包问题用贪心解决不能保证得到的是整体最优解,所以背包问题需要用动态规划来解决。
•但是经过这样三种思路的分析,应该对贪心的步骤有了一定的理解。下面来解决一下贪心能够解决的问题。

种类一:一般贪心(交换)问题

      HDU 1009 Fat Mouse’ Trade
      Fat Mouse 准备了M磅猫粮,准备和看守存放了他最喜欢的食物-咖啡豆的房间的猫进行交易。猫看守着N间房间,第i间房间存放了J[i]磅咖啡豆,交换所有咖啡豆需要F[i]磅的猫粮,FM不必交换整个房间的咖啡豆,也就是说,他可以用(F[i]*a)%磅的猫粮交换得到(J[i]*a)%磅咖啡豆。现在他请你帮忙,帮他交换到最多数量的咖啡豆。

      数据分析如下:

5

分析:

      题目描述似乎和之前的背包问题很相像,但是题目多了一个可以用一部分猫粮换取一部分咖啡豆的条件。如果那个背包问题也加入这样的条件,那就可以保证背包能够装满,这样就可以用贪心去解决。
      那么这个问题,可以选择之前的思路三,选择放前单位猫粮换取的咖啡豆最多的房间进行交易,直到猫粮用完。
      得出解决方案后,先验证一下第一组数据,三个房间分别是 3.5;1.333;2.5,先换房间1和3的,都可以全部换到。剩下房间2不能换到所有的咖啡豆,因为猫粮剩余1,只能换到1/3,那么结果就是7+5+4*(1/3)=13.333,答案正确。

      题解传送门:http://www.ocrosoft.com/?p=200
类型二:时间安排问题(区间覆盖)

      HDU 2037 今年暑假不AC
      小A列出了一些想看的电视节目,上面表明了电视节目的开始和结束时间,但是一些电视节目是冲突的,现在他想尽可能多地而且完整地看电视节目,请你帮忙。

      数据分析如下:

6

分析:

      时间安排问题,用贪心总能得到整体最优解,用数学归纳法可以证明,证明不重要,从略。
      可以先对所有的节目以结束时间从早到晚进行排序,结束时间相同的时候,按照开始时间从早到晚排序。
      然后看第一个节目,它的开始时间最早,结束时间最早,那么这个节目是一定要看的。然后后面的节目都对比前一个看的节目的结束时间,如果此时还在看上一个节目,那么继续看前一个节目,放弃这一个节目。直到分析完所有节目。

      题解传送门:http://www.ocrosoft.com/?p=204

类型三:线段覆盖问题(区间覆盖)

      这种类型和类型二非常类似,要求计算一些线段覆盖的总长度,只需要对类型二稍加修改,排序的时候先按照开始时间排序,再按结束时间排序。总长先记为线段1的全长,然后线段2和线段1比较,如果线段2不与线段1重复,总长就加上线段2的全长;如果线段2结束点在线段1结束点前,那么线段2长度不计;如果线段2与1重复且结束点不在线段1内部,则总长加上线段1结束点到线段2结束点的长度。

如下数据:答案为13。

7

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 500+10
using namespace std;
struct Node
{
    int s,f;
    bool operator<(const Node t)const
    {
        if(s==t.s)return f<t.f;
        else return s<t.s;
    }
} node[15];
int n;
int main()
{
    while(cin>>n&&n)
    {
        for(int i=0; i<n; i++)
            scanf("%d%d",&node[i].s,&node[i].f);
        int ans=node[0].f-node[0].s;
        for(int i=1,j=0;i<n;i++)
        {
            if(node[i].s>node[j].f)//如果这条线段跟前面的没有重叠
            {
                ans+=node[i].f-node[i].s;//计算这条线段的全场
                j=i;
            }
            else
            {
                if(node[i].f<=node[j].f)continue;//如果这条线段结束点在上一条线段的内部,这条线段不计长度。
                //可能会考虑如果这条线段开始比上一条长的情况,但是排序的时候已经排除了这种情况。
                ans+=node[i].f-node[j].f;
                j=i;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

类型四:数字组合问题

•这种类型可以归类到类型一中,不过类型一说是交易类型,所以这种就单独成一类好了。
•这种题目可以简单,也可以难,难题一般是思路不好想。
•例1:给出一些整数,要求对这些数字的各数位重新排序并组合,使组成的数字最大。
•解:题目说的是对数字的数位排序,那么肯定是把0-9所有数字个数统计一下,按照9 8 7…0的顺序输出即可。

   

捕获

分析:

      不能拆分的情况,有两种,1是只有一位,2是去掉0后只有一位,在判断的时候这两种可以归为一种。例:1和10000。
      能拆分的情况,一定是拆分成n-1位和1位的两个数,这个1位的数,一定取除了0以外的最小的数。n-1位的数就像例1一样,从大到小排好。题目要求输出和,进行一下大数加法就可以了。

      题解传送门:http://blog.csdn.net/jtjy568805874/article/details/51944660

      贪心算法到这里就结束了,如果有错误请指正,谢谢。

欢迎转载,请保留出处与链接。Ocrosoft » 浅谈贪心算法

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址