贪心算法(一)：活动安排问题


		对很多最优化问题来说，采用动态规划方法来解决就有点大材小用了。有时候我们可以采用贪心算法来取代。贪心算
法是通过所做的局部最佳选择来产生一个全局最优解。而且和动态规划不同的是，它是通过自顶向下的方式来解决每
一个子问题。而活动安排问题可以说是贪心算法的一个入门学习。
 
当我看到这个问题时，首先就想到了自己大一做ACM时在杭电acm里遇到的一个题目：今年暑假不AC。可以说这个题
目就是活动安排问题的翻版，只是一个讲的是怎么安排最多活动，一个讲的是最多能看到的电视节目。但本质是一样
的。下面我就以今年暑假不AC这道题目来说明吧。
 
当时看到这道题的时候想的是排序，然后暴力找。开始是按开始时间排序的，结果发现这样做没什么意义。因为有的
节目开始很早，但可能是最晚一个接受的，这样的话不能保证能得出最大值。于是便以结束时间来排序，毫无疑问，
排在最前面的那个肯定可以看，然后以这个为基础，从后依次遍历，找到第一个开始时间大于这个结束时间的节目，
并将这个节目在数组中的下标i做一个标记，并设k = i，然后从这个节目开始继续往后遍历，找出第一个节目j，使
a[j].start >= a[k].end。然后设k = j，继续往后遍历。依此循环下去，直到遍历完所有节目。实现代码如下：
[cpp] 
#include<stdio.h>  
  
struct Node  
{  
    int s;  
    int e;  
};  
  
int main()  
{  
    int n;  
    int i, j, k;  
    int count;  
    Node a[100], temp;  
  
    while (scanf("%d", &n), n)  
    {  
        for (i = 0; i < n; i++)  
        {  
            scanf("%d%d", &a[i].s, &a[i].e);  
        }  
        for (i = 0; i < n - 1; i++)  
        {  
            for (j = 0; j < n - i - 1; j++)  
            {  
                if (a[j].e > a[j + 1].e)  
                {  
                    temp = a[j];  
                    a[j] = a[j + 1];  
                    a[j + 1] = temp;  
                }  
            }  
        }  
  
        count = 1;  
        k = 0;  
        for (i = 1; i < n; i++)  
        {  
            if (a[i].s >= a[k].e)  
            {  
                k = i;  //标记选中的节目  
                count++;  
            }  
        }  
        printf("%d\n", count);  
    }  
    return 0;  
}  
 
今天看了书才知道这用到了贪心思想，下面这个代码是根据书上提供的递归形式写的，意思是一样的。
[cpp]  
#include<stdio.h>  
  
struct Node  
{  
    int s;  
    int e;  
};  
  
int count;  
  
void fun (Node a[], int i, int n)  
{  
    int m = i + 1;  
    while ((m <= n) && (a[i].e > a[m].s))  
        m++;  
  
    if (m <= n)  
    {  
        count++;  
        fun (a, m, n);  
    }  
}  
  
int main()  
{  
    int n;  
    int i, j;  
    Node a[100], temp;  
  
    while (scanf("%d", &n), n)  
    {  
        for (i = 0; i < n; i++)  
        {  
            scanf("%d%d", &a[i].s, &a[i].e);  
        }  
        for (i = 0; i < n - 1; i++)  
        {  
            for (j = 0; j < n - i - 1; j++)  
            {  
                if (a[j].e > a[j + 1].e)  
                {  www.zzzyk.com
                    temp = a[j];  
                    a[j] = a[j + 1];  
                    a[j + 1] = temp;  
                }  
            }  
        }  
  
        count = 1;  
        fun(a, 0, n-1);  
        printf("%d\n", count);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,