详解在C语言中的贪婪算法

来源:爱站网时间:2020-11-28编辑:网友分享
贪婪算法通常是为了解决问题而做出的最佳视角,也就是说:不是从全局优化,而是从某种意义上说,局部最优解,下面爱站技术频道小编就给大家详解在C语言中的贪婪算法,一起参考看看吧!

贪婪算法通常是为了解决问题而做出的最佳视角,也就是说:不是从全局优化,而是从某种意义上说,局部最优解,下面爱站技术频道小编就给大家详解在C语言中的贪婪算法,一起参考看看吧!

贪心算法

所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路如下:

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解,得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

 

实现该算法的过程:

从问题的某一初始解出发;

 while 能朝给定总目标前进一步

do 求出可行解的一个解元素;

由所有解元素组合成问题的一个可行解;

#include "stdio.h"
void main()
{ 
   int act[11][3]={{1,1,4},{2,3,5},{3,0,6},{4,5,7},{6,5,9},  
   {7,6,10},{8,8,11},{9,8,12},{10,2,13},{11,12,14}};
   greedy(act,11);
   getch();
}
int greedy(int *act,int n)
{ 
   int i,j,no;
   j=0; 
   printf("Selected activities:/n"); 
   no=0; 
   printf("Act.%2d: Start time %3d, finish time %3d/n", act[no],act[no+1],act[no+2]);
  for(i=1;i=act[j*3+2])  
       { 
         j=i; 
         printf("Act.%2d: Start time %3d, finish time %3d/n",    act[no],act[no+1],act[no+2]); 
       } 
    }
 }

 例题

    题目描述: 
    又到毕业季,很多大公司来学校招聘,招聘会分散在不同时间段,小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。 
    输入: 
    第一行n,有n个招聘会,接下来n行每行两个整数表示起止时间,由从招聘会第一天0点开始的小时数表示。 
    n     输出: 
    最多参加的招聘会个数。 
    样例输入: 
    3 
    9 10 
    10 20 
    8 15 
    样例输出: 
    2 


活动选择问题
概述
这个问题是对几个相互竞争的招聘会活动进行调度,它们都要求以独占的方式使用某一公共资源(小明)。调度的目标是找出一个最大的相互兼容的活动集合。这里是有一个需要使用某一资源(小明)的n个活动组成的集合S={a1,a2,...,an}.该资源一次只能被一个活动占用。每个活动ai有开始时间si和结束时间fi,且0 将所有的活动按照结束时间升序排列

2015816171405412.jpg (233×142)

 

定理
对于任意非空子问题Sij,设am是Sij中具有最早结束时间的活动:
fm=min{fk:ak属于Sij}
那么,
1)活动am在Sij的某最大兼容活动子集中被使用
2)子问题Sim为空,所以选择am将使子问题Smj为唯一可能非空的子问题

ac代码

  #include  
  #include  
  #include  
    
  struct join 
  { 
    int begin; 
    int end; 
  }; 
    
  int compare(const void *a, const void *b); 
    
  int main() 
  { 
    int i, n, k; 
    struct join joins[1001], temp[1001]; 
    
    while(scanf("%d", &n) != EOF) 
    { 
      for(i = 0; i = temp[k].end) 
          temp[++ k] = joins[i]; 
      } 
      printf("%d\n", k + 1); 
    } 
      
    return 0; 
  } 
    
  int compare(const void *a, const void *b) 
  { 
    const struct join *p = a; 
    const struct join *q = b; 
    
    return p->end - q->end; 
  } 

    /**************************************************************
        Problem: 1463
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:10 ms
        Memory:904 kb
    ****************************************************************/ 

以上就是爱站技术频道小编分享的详解在C语言中的贪婪算法,其实只要您拥有足够的技术和经验,这个操作是不难的。

上一篇:如何使用java线程池

下一篇:双向插入排序的算法及实现

您可能感兴趣的文章

相关阅读

热门软件源码

最新软件源码下载