C 활동 선택 문제 프로그램

활동 선택 문제는 시작 및 종료 시간이 포함된 일련의 활동이 제공되는 문제입니다. 그리고 한 사람이 한 번에 하나의 활동을 수행하면서 할 수 있는 모든 활동을 찾아야 합니다.

탐욕 알고리즘은 수행할 다음 활동을 선택하기 위해 이 문제에서 지정됩니다. 먼저 탐욕스러운 알고리즘을 이해합시다. .

탐욕적인 알고리즘 단계적으로 솔루션을 찾아 문제에 대한 솔루션을 찾으려는 알고리즘입니다. 다음 단계를 선택하기 위해 알고리즘은 가장 유망한 것으로 보이는 단계, 즉 나머지 단계에 비해 즉시 최적화된 솔루션으로 이어질 수 있는 단계도 선택했습니다. greedy 알고리즘은 전체 문제에 대한 최적의 솔루션으로 이어지는 다음 중간 단계에 대한 가장 최적화된 솔루션을 찾으려고 시도하므로 최적화 문제를 해결하는 데 사용됩니다.

탐욕적인 알고리즘은 좋은 해결책이지만 적용할 수 없는 몇 가지 문제가 있습니다. 예를 들어 0-1 배낭은 greedy 알고리즘을 사용하여 풀 수 없습니다.

알고리즘

일부 표준 탐욕 알고리즘은 다음과 같습니다. -

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