Problème de la sélection d'activités

Do you want to read our courses in English? please visit our new website cs-teachers.com Click here

Problème de la sélection d'activités

Problème ! Vous avez n activités avec leurs heures de début et de fin. Sélectionnez le nombre maximal d'activités pouvant être effectuées par une seule personne, en supposant qu'une personne ne peut travailler que sur une seule activité à la fois.
Exemple :
considérer les 3 activités suivantes triées par par heure de finition..
debut[] = {10, 12, 20};
fin[] = {20, 25, 30};
  Une personne peut effectuer au plus deux activités. activité 1 et 3

considérer les 6 activités suivantes triées par par heure de finition
debut[] = {1, 3, 0, 5, 8, 5}; fin[] = {2, 4, 6, 7, 9, 9};
  Une personne peut effectuer au plus quatre activités. (1, 2, 4 et 5)

Le choix glouton consiste à toujours choisir l'activité suivante dont l'heure de fin est la plus petite des activités restantes et l'heure de début supérieure ou égale à l'heure de fin de l'activité précédemment sélectionnée. Nous pouvons trier les activités en fonction de leur heure de fin, de sorte que nous considérions toujours la prochaine activité comme une activité de temps de finition minimum.

  1. Trier les activités en fonction de l'heure de fin
  2. Sélectionner et afficher la première activité du tableau trié
  3. Faire pour les activités restantes dans le tableau trié.
    • Si l'heure de début de cette activité est supérieure ou égale à l'heure de fin de l'activité précédemment sélectionnée, sélectionner et afficher cette activité.
                def MaxActivite(debut, fin):
                    n = len(fin)
                    print("voici les activitées selectionnées")
                
                    # choisir la première activité
                    i = 0
                    print(i+1)
                
                    for j in range(1, n):
                        if debut[j] >= fin[i]:
                            print(j+1)
                            i = j
                
                
                # Tester la fonction
                debut = [1, 3, 0, 5, 8, 5]
                fin = [2, 4, 6, 7, 9, 9]
                MaxActivite(debut, fin)
                
            
                voici les activitées selectionnées
                1
                2
                4
                5
            

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Commentaire(s)

Pour laisser un commentaire vous devez avoir un compte Inscription, ou Se connecter