貪心算法

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

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

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

2.把求解的問題分成若干個子問題。

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

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

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

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

 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<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è)季，很多大公司來學校招聘，招聘會分散在不同時間段，小明想知道自己最多能完整的參加多少個招聘會(參加一個招聘會的時候不能中斷或離開)。 
    輸入： 
    第一行n，有n個招聘會，接下來n行每行兩個整數(shù)表示起止時間，由從招聘會第一天0點開始的小時數(shù)表示。 
    n <= 1000 。 
    輸出： 
    最多參加的招聘會個數(shù)。 
    樣例輸入： 
    3 
    9 10 
    10 20 
    8 15 
    樣例輸出： 
    2 

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

定理
對于任意非空子問題Sij，設(shè)am是Sij中具有最早結(jié)束時間的活動：
fm=min{fk:ak屬于Sij}
那么，
1）活動am在Sij的某最大兼容活動子集中被使用
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
    ****************************************************************/