网易 
新闻 LOFTER 邮箱 相册 阅读 图书 有道 摄影 企业邮箱 优惠券 云笔记 闪电邮 邮箱大师 印像派 考拉海购
 
更多
博客 
手机博客 博客搬家 博客VIP服务 发现 小组 风格
 
群博客 博客油菜地 博客话题 博客热点 博客圈子 找朋友
 
登录  
 加关注
   显示下一条  |  关闭
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！立即重新绑定新浪微博》  |  关闭

AP计算机众里寻他千百度，名师成就满分路

AP计算机

导航

 
 
 
 
 

日志

 
 
关于我
千里马

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献！

文章分类

【转载】活动选择问题（动态规划算法和贪心算法）  

2016-12-21 08:47:40|  分类： 默认分类 |  标签： |举报 |字号大中小 订阅

  下载LOFTER 我的照片书  |

问题描述：

        有一个需要使用每个资源的n个活动组成的集合S= {a1，a2，···，an },资源每次只能由一个活动使用。每个活动a都有一个开始时间和结束时间，且 0<= s < f < 。一旦被选择后，活动a就占据半开时间区间[s,f]。如果[s,f]和[s,f]互不重叠，则称两个活动是兼容的。该问题就是要找出一个由互相兼容的活动组成的最大子集。

动态规划：

一、

        定义子集合Sij = { ak  S ： f i <= sk < f k <= s j}, 即每个活动都在ai结束之后开始，在aj开始之前结束，亦即Sij包含了所有和ai和aj兼容的活动。 

假设S中的活动已按照结束时间递增的顺序排列，则Sij具有如下的性质：

1.当i <= j时，Sij 为空，

2.假设ak属于Sij，那么ak将把Sij分解成两个子问题，Sij包含的活动集合就等于Sik中的活动+ak+Skj中的活动。从这里就可以看出Sij的最优子结构性质：Sij的最优解包含了子问题Sik和Skj的最优解。假设Sij的最大兼容活动子集为Aij，那么有Aij = Aik U  ak U Akj。整个活动选择问题的最优解也是S0，n+1的解。

假设c[i,j]为Sij中最大兼容子集中的活动数。则有如下递归式：

      C[i,j] =         0                       如果 Sij 为空

                       max{c[i,k] + c[k,j] +1 }  i < k < j & ak  Sij  如果Sij 不为空

根据这个递归式，可以得到一个动态规划解法。

  1. void activity_selection( const int starts[], const int finished[], int counts[][activityNum+2],int partition[][activityNum+2], const int actNum )//counts[i,j]就是C[i,j],partition[i,j]表示Sij使用哪个活动划分可以得到最大兼容活动集合  
  2. {  
  3.     int i,j,k;  
  4.   
  5.     for( i = 0; i < activityNum+2; ++i )  
  6.         for( j = 0; j < activityNum+2; ++j )  
  7.         {  
  8.                 counts[i][j] = 0;  
  9.                 partition[i][j] = 0;  
  10.         }  
  11.   
  12.     for( i = activityNum; i >=0; --i )  
  13.     {  
  14.         for( j = i+1; j < activityNum+2; ++j )  
  15.         {  
  16.                 for( k = i+1; k < j; ++k )  
  17.                 {  
  18.                     if( starts[k] >= finished[i] && finished[k] <= starts[j] )//s【i，j】不为空  
  19.                     {  
  20.                         if( counts[i][j] <= (counts[i][k] + 1 + counts[k][j]) ）                                           {  
  21.                             counts[i][j] = (counts[i][k] + 1 + counts[k][j]);  
  22.                             partition[i][j] = k;  
  23.                         }  
  24.                     }  
  25.                 }  
  26.         }  
  27.     }//for  
  28. }  

算法的时间复杂度为O（n3）。

二、

除了上面的思路外，我们还可以参照最长单调递增子序列LIS的解法，得到另外一个动态规划方法。

我们定义一个数组maxCompatibleSet，元素maxCompatibleSet[i]表示S0i中最大兼容活动子集中的活动数目，那么整个集合的最大兼容活动子集的大小就是maxCompatibleSet[n+1]。为了确定最大兼容活动子集中的活动，我们可以定义一个数组trace，

Trace[i]表示在求解maxCompatibleSet[i]时使用哪个活动对集合S0i进行划分可以得到最大的maxCompatibleSet[i]。

  1. //类似于LIS  
  2. void activitySelection( const int started[], const int finished[], int maxSetNum[], int trace[], const int activityNum )  
  3. {  
  4.     int i, j;  
  5.     for( i = 0; i < activityNum+2; ++i )  
  6.     {  
  7.         maxSetNum[i] = 1;  
  8.         trace[i] = -1;  
  9.     }  
  10.     for( i = 1; i < activityNum+2; ++i )  
  11.     {  
  12.         for( j = 1; j < i; ++j )  
  13.         {  
  14.             if( finished[j] < started[i] && maxSetNum[i] <= maxSetNum[j] )            {  
  15.                 maxSetNum[i] = maxSetNum[j]+1;   
  16.                 trace[i] = j;  
  17.             }  
  18.         }  
  19.     }  
  20. }  

该算法的时间复杂度为O（n2）。

贪心算法：

贪心算法的主要思想就是对问题求解时，总是做出在当前看来是最好的选择，产生一个局部最优解。

在活动选择问题中，每次的贪心解就是选择Sij结束时间最早的活动，这样就给后面的活动留下了目前看来最多的时间。假设活动已经按照结束时间递增的顺序进行排序，那么我们只需要遍历一次所有活动就可以得到最大兼容活动子集了。

递归版本：

  1. void recursive_activity_selector( const int started[], const int finished[],vector<int>& result, int i,int j)  
  2. {  
  3.     if( i >= j )  
  4.         return;  
  5.     int l;  
  6.     for( l = i+1; l < j; ++l )  
  7.     {  
  8.         if( started[l] >= finished[i] && finished[l] <= started[j] )   
  9.         {  
  10.             result.push_back(l);  
  11.             break;  
  12.         }  
  13.     }  
  14.     recursive_activity_selector( started, finished, result, l, j );  
  15. }  

 

迭代版本：

  1. void greedy_activity_selector( const int started[], const int finished[], vector<int>& result, int i, int j )  
  2. {  
  3.     int l;  
  4.     for( l = i+1; l < j; ++l )  
  5.     {  
  6.         if( started[l] >= finished[i] && finished[l] <= started[j] )  
  7.         {  
  8.             result.push_back(l);  
  9.             i = l;  
  10.         }  
  11.     }  
  12. }  

  评论这张
 
阅读(483)| 评论(0)

历史上的今天

评论

<#--最新日志，群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇，下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

我的照片书 - 手机博客 - 下载LOFTER APP - 订阅此博客

网易公司版权所有 ©1997-2018