[关闭]
@songpfei 2016-02-20T02:00:59.000000Z 字数 2418 阅读 975

第16章 贪心算法

算法导论


16.1 活动选择问题

 1. 动态规划求解:

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

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

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

  1. #include<stdlib.h>
  2. #include<stdio.h>
  3. #include<limits.h>
  4. #define N 11
  5. /*根据递归公式,采用自底向下的策略进行计算c[i][j],trace[n][n]保存中间划分的k值*/
  6. void DynamicActivitySelector(int*s, int*f, int c[N + 2][N + 2], int trace[N + 2][N + 2])
  7. {
  8. //1. i>=j时,c[i,j]=0 c[i,j]已初始化为0
  9. //2. i<j时,需要寻找子问题的最优解,即找到一个合适的k划分为两个子问题
  10. int temp;
  11. int imax = 0;
  12. for (int j = 1;j <N + 2;j++)
  13. for (int i = 0; i < j; i++)
  14. {
  15. //寻找k,将问题分成两个子问题c[i][k]、c[k][j]
  16. for (int k = i + 1; k < j; k++)
  17. {
  18. if (f[i] <= s[k] && f[k] <= s[j])// 判断活动k的兼容性
  19. {
  20. temp = c[i][k] + c[k][j] + 1;
  21. if (temp > c[i][j]) //找到一个最优的分界k
  22. {
  23. c[i][j] = temp;
  24. trace[i][j] = k;
  25. if (k > imax)
  26. {
  27. imax = k;
  28. printf("a%d ", imax);
  29. }
  30. }
  31. }
  32. }
  33. }
  34. }
  35. int main()
  36. {
  37. int s[N + 2] = {0,1,3,0,5,3,5,6,8,8,2,12,100};
  38. int f[N + 2] = {0,4,5,6,7,9,9,10,11,12,14,16,101};
  39. int c[N + 2][N + 2] = { 0 };
  40. int trace[N + 2][N + 2] = { 0 };
  41. DynamicActivitySelector(s, f, c, trace);
  42. printf("\nc[i][j]为:\n");
  43. for (int i = 0; i < 13; i++)
  44. {
  45. for (int j = 0; j < 13; j++)
  46. printf("%d ", c[i][j]);
  47. printf("\n");
  48. }
  49. printf("trace[i][j]为:\n");
  50. for (int i = 0; i < 13; i++)
  51. {
  52. for (int j = 0; j < 13; j++)
  53. printf("%d ", trace[i][j]);
  54. printf("\n");
  55. }
  56. system("pause");
  57. return 0;
  58. }

2. 贪心算法求解:

2.1 递归贪心算法

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

  1. RECURSIVE-ACTIVITY-SELECTOR(s,f,k,n)
  2. m=k+1
  3. while m<=n and s[m]<f[k]
  4. m=m+1
  5. if m<=n
  6. rerurn {am}URECURSIVE-ACTIVITY-SELECTOR(s,f,m,n)
  7. else
  8. return

#### 2.2 迭代贪心算法

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

C算法实现

  1. //返回兼容活动的个数
  2. int GreedyAcitivitySelector(int* start, int* final,int *solution_set,int n)
  3. {
  4. if (start == NULL || final == NULL || solution_set==NULL)
  5. return -1;
  6. int solution_count = 0;
  7. if (n >= 1)
  8. {
  9. int k = 1;
  10. solution_set[0] = k;
  11. solution_count++;
  12. for (int m = 2; m <= n; m++)
  13. {
  14. if (start[m] >= final[k])
  15. {
  16. k = m;
  17. solution_set[solution_count] = k;
  18. solution_count++;
  19. }
  20. }
  21. }
  22. return solution_count;
  23. }
  24. int main()
  25. {
  26. int solution_count;
  27. int s[12] = {0,1,3,0,5,3,5,6,8,8,2,12 };
  28. int f[12] = {0,4,5,6,7,9,9,10,11,12,14,16};
  29. int solution_set[12];
  30. solution_count = GreedyAcitivitySelector(s, f, solution_set, 12);
  31. printf("活动的最优解为:\n");
  32. for (int i = 0; i < solution_count; i++)
  33. printf("%d ", solution_set[i]);
  34. system("pause");
  35. return 0;
  36. }

16.2 贪心算法原理

1 贪心算法的一般步骤:

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

2 贪心选择的性质

  1. 通过做出局部最优解来构造全局最优解,自顶向下;
  2. 最优子结构:如果一个问题的最优解包含了其子问题的最优解,则称此问题具有最优子结构性质。
  3. 贪心对动态规划
    由于贪心和动态规划都利用了最优子结构性质,所以容易适用性混淆:
      0-1背包问题(0-1 knapsack problem): 动态规划
      分数背包问题(fractional knaosack problem):贪心选择
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注