动态规划-活动安排问题（GreedySelector）_dfreng

http://blog.sina.com.cn/u/1310376492

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

动态规划-活动安排问题（GreedySelector）

(2009-10-26 14:15:08)

标签：

杂谈

#include <stdio.h>

* n:活动个数
* start:活动开始时间
* finish:活动结束时间
* 假设输入的活动按结束时间递增序排列：finish[1] <= finish[2] <= ... <= finish[n]
* Assembly:记录所选择的集合
*/
#define MAX 100
int n,start[MAX],finish[MAX];
bool Assembly [MAX];

void Result_Print(int n,int *start,int *finish,bool Assembly[]);
void GreedySelector(int n,int *start,int *finish,bool Assembly[]);

void GreedySelector(int n,int *start,int *finish,bool Assembly[]){
   Assembly[1] = true;
   int j = 1;
   for (int i = 2;i < n;++i){
       if (start[i] >= finish[j]){
           Assembly[i] = true;
           j = i;
       }
       else Assembly[i] = false;
   }
}

void Result_Print(int n,int *start,int *finish,bool Assembly[]){
   for (int i = 0;i < n;++i){
       if (Assembly[i])
           printf("Id %d Start Time-->Finish Time : %d-->%d \n",i,start[i],finish[i]);
   }
}
int main(){
    *
   int n = 11;
   int start[] = {1,3,0,5,3,5,6,8,8,2,12};
   int finish[] = {4,5,6,7,8,9,10,11,12,13,14};
   bool A[11] = {0,};
   GreedySelector(n,start,finish,A);
    Result_Print(n,start,f,A);
   getchar();
   return 0;
   */

   printf("The common subsequence length : \n");
   scanf_s("%d",&n);
   printf("The start time subsequence : \n");
   for (int i = 0;i < n;++i)
       scanf_s("%d",&start[i]);
   printf("The finish time subsequence : \n");
   for (int i = 0;i < n;++i)
       scanf_s("%d",&finish[i]);
   getchar();
   GreedySelector(n,start,finish,Assembly);
    Result_Print(n,start,finish,Assembly);
   getchar();
   return 0;
}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：动态规划之最长公共子序列算法

后一篇：C++文件读写总结

新浪BLOG意见反馈留言板　欢迎批评指正