Chinaunix首页 | 论坛 | 博客
  • 博客访问: 448750
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: C/C++

2011-09-11 18:21:20

一 简介

当遇到最优值问题时,往往采用的是动态规划算法,而采用动态规划计算获取的最优解是通过无数而且重复的子问题时,就非常有效。根据算法导论上的讲解,顺序如下:

1.分析最优解的结构

2.定义出解的递归表达式

3.进行自底向上的求值

4.从子问题中构造一个最优解

其中定义出 一个好的递归定义式是关键,递归式分析以下几种:

1.如果找出第i项与第i-1项之间的关系/理想情况

2.如果找出第i项与第k项之间的关系/一般情况

另外,在进行自底向上的求解过程中,采用的循环起始点需要进行考究,以满足自底向上的特征,递归式一般形式为:

1.s[i] = min/max{s[k] + f(k)};起始条件

2.s[i,j] = min/max{s[i,k]+s[k+1,j]};子问题的起始循环条件

其中f[k]为代价函数,这里面的s[i,j],d[i]:一般情况下为前面i项的和形式,这样才能更好的列出递归公式。

二 例题

求数组最长递增子序列

最为普通的方法就是采用递归式2,递归式如下:

其中l[i,k]:ik的递增序列最小值,m[k+1,j]:k+1j的递增序列中最大值

上面的式子都需要更新两个数组:l[i,j] = l[i,k],m[i,j] = m[k+1,j]

相应的代码如下:

  1. void increase1(int a[],int size)
  2. {
  3. int s[size][size],i,j,k;
  4. int m[size][size],l[size][size];
  5. //m[i][j]:i到j中递增记录中的最后一个元素
  6. //l[i][j]:i到j中递增记录中的第一个元素
  7. //s[i][j]:i到j中的递增记录的长度
  8. for(i=0;i
  9. {
  10. for(j=0;j
  11. {
  12. m[i][j] = a[j];
  13. l[i][j] = a[j];
  14. s[i][j] = 1;
  15. }
  16. s[i][i] = 1;
  17. m[i][i] = a[i];
  18. l[i][i] = a[i];
  19. if((i+1)
  20. s[i][i+1] = 2;
  21. m[i][i+1] = a[i+1];
  22. l[i][i+1] = a[i];
  23. }
  24. }
  25. for(i=size-3;i>=0;i--)
  26. for(j=i+2;j
  27. for(k=i;k
  28. {
  29. if(s[i][j] < (s[i][k] + s[k+1][j]) && m[i][k] < l[k+1][j])
  30. {
  31. s[i][j] = s[i][k]+s[k+1][j];
  32. l[i][j] = l[i][k];
  33. m[i][j] = m[k+1][j];
  34. }
  35. else if(s[i][j] == (s[i][k] + s[k+1][j]) && m[k+1][j]
  36. {
  37. m[i][j] = m[k+1][j];
  38. s[i][j] = s[i][k] + s[k+1][j];
  39. l[i][j] = l[i][k];
  40. }
  41. printf("i:%d,j:%d,k:%d,s[%d][%d]:%d,s[%d][%d]:%d,s[%d][%d]:%d,\
  42. m[%d][%d]:%d,l[%d][%d]:%d\n",i,j,k,i,j,s[i][j],i,k,s[i][k],k+1,j,s[k+1][j],i,j,m[i][j],i,j,l[i][j]);
  43. }
  44. for(i=0;i
  45. for(j=0;j
  46. printf("m[%d][%d]:%d,l[%d][%d]:%d\n",i,j,m[i][j],i,j,l[i][j]);
  47. printf("0-->%d:%d\n",size-1,s[0][size-1]);
  48. }

为了降低复杂度,就需要采用递归式2,采用直接套用上面的方法列出递归式2如下:

与之对应的程序如下:

  1. //s[j] = max{1+s[i]} 0<i<j s[i]:以元素i为尾的长度
  2. void increase2(int a[],int size)
  3. {
  4.     int s[size],i,j;
  5.     int max;

  6.     for(i=0;i<size;i++)    s[i] = 1;
  7.     
  8.     max = INT_MIN;

  9.     for(i=0;i<size;i++)
  10.      for(j=i+1;j<size;j++)
  11.     {
  12.      if(a[i]<=a[j] && s[j]<(1+s[i]))
  13.      {
  14.         s[j] = 1+s[i];
  15.         max = max < s[j]?s[j]:max;
  16.      }
  17.      printf("i:%d,s[%d]:%d\n",i,j,s[j]);    
  18.     }

  19.     printf("max:%d\n",max);
  20. }

现在仍然需要想办法来降低复杂度,通过分析程序发现,第二重循环为一查找过程,通过查找递增,并且长度大的序列,不妨将其事先进行保存在一个有序序列中,这样就会降低复杂度,即下面的程序:

  1. int increase3(int a[],int size)
  2. {
  3. int i,j,k,mid;
  4. //l[i]:记录长度为i+1的最后一个元素
  5. //d[i]:结尾为a[i]的递增序列长度
  6. int l[size],d[size];
  7. for(i=0;i
  8. {
  9. d[i] = 1;
  10. l[i] = 0;
  11. }
  12. d[0] = 1;
  13. l[0] = a[0];
  14. j = 0;
  15. for(i=1;i
  16. {
  17. //从0~j查找满足条件的最后一个元素
  18. k = 0;
  19. while(k
  20. {
  21. mid = (k+j)/2;
  22. if(a[i]
  23. else k = mid+1;
  24. }
  25. printf("before k:%d,j:%d,l[%d]:%d,d[%d]:%d,a[%d]:%d\n",\
  26. k,j,k,l[k],i,d[i],i,a[i]);
  27. if(l[k] < a[i]) {
  28. d[i] = k+1;
  29. if(l[k+1]==0 ||l[k+1]>a[i])
  30. l[k+1] = a[i];
  31. j = k+1;
  32. }
  33. else {
  34. l[k] = a[i];
  35. j = k;
  36. }
  37. printf(" after k:%d,j:%d,l[%d]:%d,d[%d]:%d,a[%d]:%d\n",\
  38. k,j,k,l[k],i,d[i],i,a[i]);
  39. }
  40. // for(i=0;i
  41. // printf("increase3 l[%d]:%d\n",i,l[i]);
  42. printf("max:%d\n",j+1);
  43. }

参考资料:

1.算法导论

2.编程之美

3.一些网上LaTex资料

阅读(1086) | 评论(0) | 转发(1) |
0

上一篇:Linux进程调度(一)

下一篇:Linux调度器

给主人留下些什么吧!~~