贪心算法

贪心算法总结

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本思路

1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一子问题求解，得到子问题的局部最优解；
4. 把子问题的解局部最优解合成原来解问题的一个解。

算法实现

1. 从问题的某个初始解出发。
2. 采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。
3. 将所有部分解综合起来，得到问题的最终解。

实例分析

实例 1 背包问题

• 问题描述有一个背包，背包容量是 M=150。有 7 个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

  ​

  ​

  

• 问题分析

  ​

  1.目标函数： ∑pi 最大，使得装入背包中的所有物品 pi 的价值加起来最大。

  ​

  2.约束条件：装入的物品总重量不超过背包容量：∑wi<=M( M=150)

  ​

  3.贪心策略：

  • 选择价值最大的物品
  • 选择价值最大的物品
  • 选择单位重量价值最大的物品有三个物品 A,B,C，其重量分别为{30,10,20}，价值分别为{60,30,80}，背包的容量为 50，分别应用三种贪心策略装入背包的物品和获得的价值如下图所示：

三种策略

• 算法设计：

1. 计算出每个物品单位重量的价值
2. 按单位价值从大到小将物品排序
3. 根据背包当前所剩容量选取物品
4. 如果背包的容量大于当前物品的重量，那么就将当前物品装进去。否则，那么就将当前物品舍去，然后跳出循环结束。

• 代码实现

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct{
    int w;
    int v;
    double avg;
}P;
bool cmp(P a,P b){
    return a.avg>b.avg;
}
int main(){
    P *p;
    int n,i,m;//n 物品个数 m背包容量
    while(cin>>n>>m){
        p=new P[n];
        for(i=0;i<n;i++){
            cin>>p[i].w>>p[i].v;
            p[i].avg=p[i].v/p[i].w*1.0;
        }
        sort(p,p+n,cmp);
        int maxvalue=0;
        for(i=0;i<n;i++){
            if(p[i].w<=m){
                m-=p[i].w;
                maxvalue+=p[i].v;
            }else{
                break;
            }
        }
        cout<<maxvalue<<endl;
    }
    return 0;
}

• 运行结果

  ​

  ​

  

实例 2 活动安排问题

• 问题描述：设有 n 个活动的集合 E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi,且 si <fi 。要求设计程序，使得安排的活动最多。

(ps:活动结束时间按从小到大排序)

• 问题分析：活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可提供一个简单、漂亮的方法，使尽可能多的活动能兼容的使用公共资源。设有 n 个活动的集合｛0，1，2，…，n-1｝，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 starti 和一个结束时间 endi，且 starti<endi。如选择了活动 i，则它在半开时间区间[starti,endi）内占用资源。若区间[starti,endi)与区间[startj,endj)不相交，称活动 i 与活动 j 是相容的。也就是说，当 startj≥endi 或 starti≥endj 时，活动 i 与活动 j 相容。活动安排问题就是在所给的活动集合中选出最多的不相容活动。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
• 算法设计：若被检查的活动 i 的开始时间 starti 小于最近选择的活动 j 的结束时间 endj，则不选择活动 i，否则选择活动 i 加入集合中。运用该算法解决活动安排问题的效率极高。当输入的活动已按结束时间的非减序排列，算法只需 O(n)的时间安排 n 个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用 O(nlogn)的时间重排。
• 代码实现：代码 1

#include<iostream>
#include<algorithm>
using namespace std;
struct actime{
    int start,finish;
}act[1002];
bool cmp(actime a,actime b){
    return a.finish<b.finish;
}
int main(){
    int i,n,t,total;
    while(cin>>n){//活动的个数
        for(i=0;i<n;i++){
            cin>>act[i].start>>act[i].finish;
        }
        sort(act,act+n,cmp);//按活动结束时间从小到大排序
        t=-1;
        total=0;
        for(i=0;i<n;i++){
            if(t<=act[i].start){
                total++;
                t=act[i].finish;
            }
        }
        cout<<total<<endl;
    }
    return 0;
}

• 运行结果 1

  ​

  ​

  

代码 2

#include <iostream>
using namespace std;

template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[]);

const int N = 11;

int main()
{
    //下标从1开始,存储活动开始时间
    int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};

    //下标从1开始,存储活动结束时间
    int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};

    bool A[N+1];

    cout<<"各活动的开始时间,结束时间分别为："<<endl;
    for(int i=1;i<=N;i++)
    {
        cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
    }
    GreedySelector(N,s,f,A);
    cout<<"最大相容活动子集为："<<endl;
    for(int i=1;i<=N;i++)
    {
        if(A[i]){
            cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
        }
    }

    return 0;
}

template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[])
{
    A[1]=true;
    int j=1;//记录最近一次加入A中的活动

    for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容
    {
        if (s[i]>=f[j])
        {
            A[i]=true;
            j=i;
        }
        else
        {
            A[i]=false;
        }
    }
}

• 运行结果 2

实例 3 最小生成树（克鲁斯卡尔算法）

• 问题描述

求一个连通无向图的最小生成树的代价（图边权值为正整数）。

输入

第一行是一个整数 N（1<=N<=20），表示有多少个图需要计算。以下有 N 个图，第 i 图的第一行是一个整数 M（1<=M<=50），表示图的顶点数，第 i 图的第 2 行至 1+M 行为一个 M*M 的二维矩阵，其元素 ai,j 表示图的 i 顶点和 j 顶点的连接情况，如果 ai,j=0，表示 i 顶点和 j 顶点不相连；如果 ai,j>0，表示 i 顶点和 j 顶点的连接权值。

输出

每个用例，用一行输出对应图的最小生成树的代价。

样例输入

1
6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0

样例输出

15

• Kruskal 算法简述假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1 条边为止。

• 模拟过程：

  ​

  ​

  

  模拟过程

• 算法难点：（1）边的选择要求从小到大选择，则开始显然要对边进行升序排序。（2）选择的边是否需要，则从判断该边加入后是否构成环入手。

• 算法设计：（1）对边升序排序在此采用链式结构，通过插入排序完成。每一结点存放一条边的左右端点序号、权值及后继结点指针（2）边的加入是否构成环一开始假定各顶点分别为一组，其组号为端点序号。选择某边后，看其两个端点是否在同一组中，即所在组号是否相同，如果是，表示构成了环，则舍去。 如果两个端点所在的组不同，则表示可以加入，则将该边两端的组合并成同一组。

• 代码实现：

#include<iostream>
using namespace std;
struct node
{
 int l;
 int r;
 int len;
 node *next;
};
void insert(node *&h,node *p)   //指针插入排序
{
 node *q=h;
 while(q->next && q->next->len <= p->len)
 {
  q=q->next;
 }
 p->next=q->next;
 q->next=p;
}
int main()
{
// freopen("001.in","r",stdin);
 node *h,*p;
 int n,m,x,temp;
 int *a;
 int i,j;
 int sum;
 cin>>n;
 while(n--)
 {
  sum=0;
  cin>>m;
  a=new int[m+1];
  for (i=1;i<=m;i++)
  {
   a[i]=i;
  }
  h=new node;
  p=h;
  p->next=NULL;
  for (i=1;i<=m;i++)
   for (j=1;j<=m;j++)
   {
    cin>>x;
    if (i>j && x!=0)
    {
     p=new node;
     p->l=i;
     p->r=j;
     p->len=x;
     p->next=NULL;
     insert(h,p);   //调用插入排序
    }
   }
          p=h->next;
   while (p)
   {
    if (a[p->l]!=a[p->r])
    {

     sum+=p->len;
     temp=a[p->l];
     for(i=1;i<=m;i++)
      if (a[i]==temp)
      {
       a[i]=a[p->r];
      }
    }
   p=p->next;
   }
   /*   可以测试程序工作是否正常
   p=h->next;
   while(p)
   {
    cout<<p->l<<':';cout<<p->r<<' ';
    cout<<p->len<<"   ";
    p=p->next;
   }
   */
   cout<<sum<<endl;
 }
 return 0;
}

• 运行结果

  ​

  ​

  

  image.png

实例 4 hdu1050-Moving Tables

• 题目描述

在一个狭窄的走廊里将桌子从一个房间移动到另一个房间，走廊的宽度只能允许一个桌子通过。给出 t，表示有 t 组测试数据。再给出 n，表示要移动 n 个桌子。n 下面有 n 行，每行两个数字，表示将桌子从 a 房间移到 b 房间。走廊的分布图如一图所示，每移动一个桌子到达目的地房间需要花 10 分钟，问移动 n 个桌子所需要的时间。

• 输入

3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50

• 输出

10
20
30

• 解题思路若移动多个桌子时，所需要经过的走廊没有重合处，即可以同时移动。若有一段走廊有 m 个桌子都要经过，一次只能经过一个桌子，则需要 m*10 的时间移动桌子。 设一个数组，下标值即为房间号。桌子经过房间时，该房间号为下标对应的数组值即加 10。最后找到最大的数组值，即为移动完桌子需要的最短时间。(以上为代码 2，代码 3 同这个思想)
  注意：

1. 可能出发位置比目的地房间大,无论大小，我们都可以看做从小的房间移动到大的房间

2. 出发房间为偶数则减一，结束房间为奇数则加一

   ​

   ​

   

   ​

   我们首先输入每次移动的出发和结束房间，然后按每次移动的出发房间从小到大排序，然后直至所有的房间移动完毕。（代码 1 的解释）

• 代码 1（我自己感觉不是贪心算法，属于暴力破解吧，大家酌情考虑）

#include<iostream>
#include<algorithm>
using namespace std;

struct table{
    int from,to;
    bool flag;//记录改房间是否被访问过
}moving[205];

bool cmp(table a,table b){
    return a.from<b.from;
}

int main(){
    int i,T,n;//T代表测试实例个数，n代表每个测试下的table个数
    cin>>T;
    while(T--){
        cin>>n;
        for(i=0;i<n;i++){
            cin>>moving[i].from>>moving[i].to;
            if(moving[i].from > moving[i].to)
            {
                int temp = moving[i].from;
                moving[i].from = moving[i].to;
                moving[i].to = temp;
            }//可能出发位置比目的地房间大,无论大小，我们都可以看做从小的房间移动到大的房间
            if(moving[i].from%2==0){//考虑实际情况，出发房间为偶数是减一，可参照题中给出的图一
                moving[i].from--;
            }
            if(moving[i].to%2==1){//考虑实际情况，结束房间为奇数是加一，
                moving[i].to++;
            }
            moving[i].flag=false;//初始化房间未被访问过
        }
        sort(moving,moving+n,cmp);//将所有table按出发房间从小到大排序;
        bool completion=false;//是否所有的table移动结束
        int cnt=-1,priorTo;//priorTo 记录前一个table移动结束的房间
        while(!completion){
            completion=true;
            cnt++;
            priorTo=0;
            for(i=0;i<n;i++){//每一轮将可以同时移动的table全部移动完：比如2->5,6->10，因为他们没有共用走廊
                if(!moving[i].flag&&moving[i].from>priorTo){
                    moving[i].flag=true;//标记当前table已经移动完毕
                    priorTo=moving[i].to;
                    completion=false;
                }
            }
        }
        cout<<cnt*10<<endl;
    }
    return 0;
}

• 代码 1 运行结果

  ​

  ​

  

• 代码 2

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int t,n,count[410],i,start,end,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(count,0,sizeof(count));
        while(n--)
        {
            scanf("%d%d",&start,&end);
            if(start>end)//可能出发位置比目的地房间大。
            {            //无论大小，我们都可以看做从小的房间移动到大的房间
                k=start;
                start=end;
                end=k;
            }
            if(start%2==0)//考虑实际情况，出发房间为偶数是减一，可参照题中给出的图一
               start-=1;
            if(end%2==1)//目的地房间为奇数时加一
               end+=1;
            for(i=start;i<=end;++i)
               count[i]+=10;
        }
        printf("%d\n",*max_element(count,count+400));//STL中寻找数列最大值函数
    }
    return 0;
}

• 代码 3

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAXN 500
using namespace std;
struct temp{
    int be,en;
};
bool comp(temp a,temp b){
    return a.be<b.be;
}
int main(){
    temp my[MAXN];
    int m,n,i;
    cin>>m;
    while(m--){
        cin>>n;
        i=0;
        int a,b,j;
        while(i<n){
            cin>>a>>b;
            if(a>b)a^=b^=a^=b;
            my[i].be=(a+1)/2;
            my[i++].en=(b+1)/2;
        }
        sort(my,my+n,comp);
        int s=0,out=n,t=0;
        int aa[203];
        memset(aa,0,sizeof(aa));
       for(i=0;i<n;++i){
            for(j=my[i].be;j<=my[i].en;++j)aa[j]++;
       }
       sort(aa,aa+200);
        cout<<aa[199]*10<<'\12';
    }
    return 0;
}