@songpfei 2016-02-20T02:00:59.000000Z 字数 2418 阅读 1086

# 第16章 贪心算法

算法导论

## 16.1 活动选择问题

### 1. 动态规划求解：

c[i,j]为集合$S_{ij}$的最优解大小，则递归式为：

#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+1while m<=n and s[m]<f[k]    m=m+1if 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=mreturn 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):贪心选择

• 私有
• 公开
• 删除