활동 선택 문제에 대한 C 프로그램

활동 선택 문제는 일련의 활동과 시작 및 종료 시간이 주어지는 문제입니다. 우리는 사람이 하나의 활동을 동시에 수행하면서 수행할 수 있는 모든 활동을 찾아야 합니다.

이 문제는 수행할 다음 활동을 선택하는 그리디 알고리즘을 지정합니다. 먼저 탐욕 알고리즘을 이해해 봅시다.

탐욕 알고리즘은 단계별로 해결책을 찾아 문제에 대한 해결책을 찾으려는 알고리즘입니다. 다음 단계를 선택하기 위해 알고리즘은 가장 유망해 보이는 단계, 즉 나머지 단계와 비교하여 즉시 최적화된 솔루션으로 이어지는 단계도 선택합니다. 탐욕 알고리즘은 다음 중간 단계에 대한 가장 최적의 솔루션을 찾으려고 시도하여 전체 문제에 대한 최적의 솔루션을 이끌어 내기 때문에 최적화 문제를 해결하는 데 사용됩니다.

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

Algorithm

일부 표준 그리디 알고리즘은 -

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]

여기에서는 최대 2가지 활동을 수행할 수 있습니다. 수행할 수 있는 활동은 [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

위 내용은 활동 선택 문제에 대한 C 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!