貪心算法

所謂貪心算法是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。

貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法的基本思路如下：

1.建立數(shù)學(xué)模型來描述問題。

2.把求解的問題分成若干個(gè)子問題。

3.對(duì)每一子問題求解，得到子問題的局部最優(yōu)解。

4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。

實(shí)現(xiàn)該算法的過程：

從問題的某一初始解出發(fā)；

 while 能朝給定總目標(biāo)前進(jìn)一步

do 求出可行解的一個(gè)解元素；

由所有解元素組合成問題的一個(gè)可行解；

#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<n;i++) 
  {  
    no=i*3; 
    if(act[no+1]>=act[j*3+2])  
       { 
         j=i; 
         printf("Act.%2d: Start time %3d, finish time %3d/n",    act[no],act[no+1],act[no+2]); 
       } 
    }
 }

 例題

    題目描述： 
    又到畢業(yè)季，很多大公司來學(xué)校招聘，招聘會(huì)分散在不同時(shí)間段，小明想知道自己最多能完整的參加多少個(gè)招聘會(huì)(參加一個(gè)招聘會(huì)的時(shí)候不能中斷或離開)。 
    輸入： 
    第一行n，有n個(gè)招聘會(huì)，接下來n行每行兩個(gè)整數(shù)表示起止時(shí)間，由從招聘會(huì)第一天0點(diǎn)開始的小時(shí)數(shù)表示。 
    n <= 1000 。 
    輸出： 
    最多參加的招聘會(huì)個(gè)數(shù)。 
    樣例輸入： 
    3 
    9 10 
    10 20 
    8 15 
    樣例輸出： 
    2 

活動(dòng)選擇問題
概述
這個(gè)問題是對(duì)幾個(gè)相互競爭的招聘會(huì)活動(dòng)進(jìn)行調(diào)度，它們都要求以獨(dú)占的方式使用某一公共資源（小明）。調(diào)度的目標(biāo)是找出一個(gè)最大的相互兼容的活動(dòng)集合。這里是有一個(gè)需要使用某一資源（小明）的n個(gè)活動(dòng)組成的集合S={a1,a2,...,an}.該資源一次只能被一個(gè)活動(dòng)占用。每個(gè)活動(dòng)ai有開始時(shí)間si和結(jié)束時(shí)間fi，且0<=si<fi<無窮。一旦被選擇后，活動(dòng)ai就占據(jù)了區(qū)間[si,fi].如果區(qū)間[si,fi]和[sj,fj]互不重疊，稱活動(dòng)ai和aj是兼容的?；顒?dòng)選擇問題就是要選擇出一個(gè)由互相兼容的問題組成的最大子集合。
將所有的活動(dòng)按照結(jié)束時(shí)間升序排列

定理
對(duì)于任意非空子問題Sij，設(shè)am是Sij中具有最早結(jié)束時(shí)間的活動(dòng)：
fm=min{fk:ak屬于Sij}
那么，
1）活動(dòng)am在Sij的某最大兼容活動(dòng)子集中被使用
2）子問題Sim為空，所以選擇am將使子問題Smj為唯一可能非空的子問題

ac代碼

  #include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
    
  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 < n; i ++) 
      { 
        scanf("%d %d", &joins[i].begin, &joins[i].end); 
      } 
        
      qsort(joins, n, sizeof(joins[0]), compare); 
    
      k = 0; 
      temp[k] = joins[0]; 
      for(i = 1; i < n; i ++) 
      { 
        if(joins[i].begin >= 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
    ****************************************************************/ 

最新評(píng)論