《算法导论》16.1节－贪心算法之活动选择问题

1.递归解决：

#include <stdio.h>
int s[11] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int f[11] = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int a[11];

static int select(int s[], int f[], int i, int n);
int main(int argc, char **argv)
{
        int i;

        select(s, f, 0, 10);
        for(i = 0; i < 11; i++){
                if(a[i]){
                        printf("%d ", i+1);
                }
        }
        printf("\n");

        return 0;
}

static int select(int s[], int f[], int i, int n)
{
        int m;

        a[i] = 1;
        m = i + 1;

        while((m <= n) && (s[m] <= f[i])){
                m = m + 1;
        }
        if(m <= n){
                a[m] = 1;
                i = m;
                select(s, f, m, n);
        }

        return 0;
}


2.迭代解决：

#include <stdio.h>

int s[11] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int f[11] = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int a[11];

int main(int argc, char **argv)
{
        int i, m, len = 11;

        a[0] = 1;
        i = 0;
        for(m = 1; m < 11; m++){
                if(s[m] >= f[i]){
                        a[m] = 1;
                        i = m;
                }
        }

        for(i = 0; i < 11; i++){
                if(a[i]){
                        printf("%d ", i+1);
                }
        }
        printf("\n");

        return 0;
}
~

3.执行结果：
[xxxx@localhost suanfa]$ ./a.out
1 4 8 11