Programme C pour le problème de sélection d'activité

Le problème de sélection d'activités est un problème étant donné un ensemble d'activités et leurs heures de début et de fin. Nous devons trouver toutes les activités qu’une personne peut effectuer en effectuant une seule activité à la fois.

Ce problème spécifie un algorithme glouton pour choisir la prochaine activité à effectuer. Comprenons d’abord l’algorithme gourmand.

L'algorithme gourmand est un algorithme qui tente de trouver une solution à un problème en trouvant une solution étape par étape. Pour choisir l’étape suivante, l’algorithme sélectionne également l’étape qui semble la plus prometteuse, c’est-à-dire celle qui conduit à une solution optimisée immédiatement par rapport aux autres. L'algorithme glouton est utilisé pour résoudre des problèmes d'optimisation car il tente de trouver la solution la plus optimale pour la prochaine étape intermédiaire, conduisant à la solution optimale à l'ensemble du problème.

Bien que l'algorithme glouton soit une bonne solution, certains problèmes empêchent son application. Par exemple, le sac à dos 0-1 ne peut pas être résolu à l’aide d’un algorithme glouton.

Algorithme

Certains algorithmes gloutons standards sont -

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

Problème de sélection inactive, on nous pose n problèmes avec l'heure de début et de fin. Nous devons choisir le nombre maximum d’activités qu’une personne peut effectuer, en supposant qu’elle ne peut effectuer qu’une seule activité à la fois.

Il y a 3 activités triées par heure de fin,

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

Ici, on peut réaliser jusqu'à deux activités. Les activités pouvant être réalisées sont [0, 2].

Exemple

Démonstration

#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;
}

Sortie

Following activities are selected 0 2

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!