活动选择问题的C程序

活动选择问题是一个给我们提供了一系列活动的开始和结束时间的问题。我们需要找到一个人一次可以执行的所有活动。

在此问题中指定了贪婪算法，以选择要执行的下一个活动。首先让我们了解贪婪算法。

贪婪算法是一种试图通过逐步找到解决方案来找到问题解决方案的算法。为了选择下一步，算法还选择了最有希望的步骤，即与其余步骤相比，可以立即导致优化的解决方案。贪婪算法用于解决优化问题，因为它试图为下一个中间步骤找到最优化的解决方案，从而导致整个问题的最优解决方案。

尽管贪心算法是一个很好的解决方案，但存在一些无法应用的问题。例如，使用贪婪算法无法解决0-1背包问题。

算法

一些标准的贪婪算法是-

1) Dijkstrata’s Shortest Path
2) Minimum Spanning Tree (MST) {prim’s and kruskal’s}
3) Huffman coding

不活动选择问题，给我们n个开始和结束时间的问题。假设一个人可以在某个时间点进行一项活动，那么我们需要选择一个人可以执行的最大活动数。

共有3项活动，按照完成时间排序，

Start = [1 , 5 , 12 ]
End = [10, 13, 23]

在此，此人最多只能执行两个活动。可以执行的活动是[0，2]。

示例

#include<stdio.h>
int main(){
   int start[] = {1 , 5 , 12};
   int finish[] = {10, 13, 23};
   int activities = sizeof(start)/sizeof(start[0]);
   int i, j;
   printf ("Following activities are selected \t");
   i = 0;
   printf("%d\t", i);
   for (j = 1; j < activities; j++){
      if (start[j] >= finish[i]){
         printf ("%d ", j);
         i = j;
      }
   }
   return 0;
}

输出结果

Following activities are selected 0 2