第16章 贪心算法

算法导论

16.1 活动选择问题

　1. 动态规划求解：

活动选择问题具有最优子结构，另$S_{ij}$表示在$a_i$结束之后开始，球在$a_j$开始之前结束的那些活动子集。
c[i,j]为集合$S_{ij}$的最优解大小，则递归式为：

参考：http://www.cnblogs.com/Anker/archive/2013/03/16/2963625.html

为了方便讨论和后面的计算，添加两个虚构活动a0和an+1，其中f0=0，sn+1=∞。
动态规划c代码实现：

#include<stdlib.h>
#include<stdio.h>
#include<limits.h>
#define N 11
/*根据递归公式，采用自底向下的策略进行计算c[i][j]，trace[n][n]保存中间划分的k值*/
void DynamicActivitySelector(int*s, int*f, int c[N + 2][N + 2], int trace[N + 2][N + 2])
{
    //1. i>=j时，c[i,j]=0  c[i,j]已初始化为0
    //2. i<j时，需要寻找子问题的最优解，即找到一个合适的k划分为两个子问题
    int temp;
    int imax = 0;
    for (int j = 1;j <N + 2;j++)
        for (int i = 0; i < j; i++)
        {
            //寻找k，将问题分成两个子问题c[i][k]、c[k][j] 
            for (int k = i + 1; k < j; k++)
            {
                if (f[i] <= s[k] && f[k] <= s[j])// 判断活动k的兼容性
                {
                    temp = c[i][k] + c[k][j] + 1;
                    if (temp > c[i][j]) //找到一个最优的分界k
                    {
                        c[i][j] = temp;
                        trace[i][j] = k;
                        if (k > imax)
                        {
                            imax = k;
                            printf("a%d ", imax);
                        }
                    }
                }
            }
        }
}
int main()
{
    int s[N + 2] = {0,1,3,0,5,3,5,6,8,8,2,12,100};
    int f[N + 2] = {0,4,5,6,7,9,9,10,11,12,14,16,101};
    int c[N + 2][N + 2] = { 0 };
    int trace[N + 2][N + 2] = { 0 };
    DynamicActivitySelector(s, f, c, trace);
    printf("\nc[i][j]为：\n");
    for (int i = 0; i < 13; i++)
    {
        for (int j = 0; j < 13; j++)
            printf("%d  ", c[i][j]);
        printf("\n");
    }
    printf("trace[i][j]为：\n");
    for (int i = 0; i < 13; i++)
    {
        for (int j = 0; j < 13; j++)
            printf("%d  ", trace[i][j]);
        printf("\n");
    }
    system("pause");
    return 0;
}

2. 贪心算法求解：

2.1 递归贪心算法

ACTIVITY-SELECTOR(s,f,0,n)

RECURSIVE-ACTIVITY-SELECTOR(s,f,k,n)
m=k+1
while m<=n and s[m]<f[k]
    m=m+1
if m<=n
   rerurn {am}URECURSIVE-ACTIVITY-SELECTOR(s,f,m,n)
else
   return ∅

#### 2.2 迭代贪心算法

GREEDY-ACTIVITY-SELECTOR(s,f)
 n=s.length
 A={a1}
 k=1  //子集中最早结束的活动ak
 for m=2 to n
    if(s[m]>=f[k])
      A=A U {am}
      k=m
return A

C算法实现

//返回兼容活动的个数
int GreedyAcitivitySelector(int* start, int* final,int *solution_set,int n)
{
    if (start == NULL || final == NULL || solution_set==NULL)
        return -1;
    int solution_count = 0;
    if (n >= 1)
    {
        int k = 1;
        solution_set[0] = k;
        solution_count++;
        for (int m = 2; m <= n; m++)
        {
            if (start[m] >= final[k])
            {
                k = m;
                solution_set[solution_count] = k;
                solution_count++;
            }
        }
    }
    return solution_count;
}
int main()
{
    int solution_count;
    int s[12] = {0,1,3,0,5,3,5,6,8,8,2,12 };
    int f[12] = {0,4,5,6,7,9,9,10,11,12,14,16};
    int solution_set[12];
    solution_count = GreedyAcitivitySelector(s, f, solution_set, 12);
    printf("活动的最优解为：\n");
    for (int i = 0; i < solution_count; i++)
        printf("%d  ", solution_set[i]);
    system("pause");
    return 0;
}

16.2 贪心算法原理

1 贪心算法的一般步骤：

1. 将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解；
2. 证明做出贪心选择后，原问题总是存在最优解
3. 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题最优解，这样就得到最优子结构；

2 贪心选择的性质

1. 通过做出局部最优解来构造全局最优解，自顶向下；
2. 最优子结构：如果一个问题的最优解包含了其子问题的最优解，则称此问题具有最优子结构性质。
3. 贪心对动态规划
   由于贪心和动态规划都利用了最优子结构性质，所以容易适用性混淆：
     0-1背包问题（0-1 knapsack problem): 动态规划
     分数背包问题（fractional knaosack problem):贪心选择