Algorithmes Gloutons

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Problème de séquencement des tâches

Problème ! Étant donné un ensemble de travaux pour lesquels chaque travail a une date limite et les bénéfices associés si le travail est terminé avant la date limite. Il est également indiqué que chaque travail prend une seule unité de temps, de sorte que le délai minimum possible pour tout travail est 1. Comment maximiser le profit total si un seul travail peut être planifié à la fois.
Exemple :
travaildate limitebénéfice
a420
b110
c140
d130

  Ce qui suit est la séquence de profit maximum des travaux (c,a)

  1. Triez tous les travaux par ordre décroissant de profit.
  2. Initialisez la séquence de résultats avec le premier travail dans les travaux triés.
  3. Faire pour les travaux restant (n-1)
    • Si le travail en cours peut tenir dans la séquence de résultats actuelle sans manquer la date limite, ajoutez le au résultat. Sinon ignorer le travail en cours.
# travaux : liste des travaux
# creneaux : nombre de créneaux horaires
def Sequencement(travaux, creneaux):

    # nombre de travaux
    n = len(travaux)

    # Trier les travaux dans l'ordre décroissant des bénéfices
    for i in range(n):
        for j in range(n - 1 - i):
            if travaux[j][2] < travaux[j + 1][2]:
                travaux[j], travaux[j + 1] = travaux[j + 1], travaux[j]

    # créneaux disponibles
    result = [False] * creneaux

    # résultat
    job = []

    # pour chaque travail
    for i in range(len(travaux)):

        # trouver créneau disponible
        for j in range(min(creneaux - 1, travaux[i][1] - 1), -1, -1):

            # créneau disponible
            if result[j] is False:
                result[j] = True
                job.append(travaux[i][0])
                break

    print(job)


# tester la fonction
travaux = [['a', 4, 20],  # travaux
           ['b', 1, 10],
           ['c', 1, 40],
           ['d', 1, 30]]


print("Ce qui suit est la séquence de profit maximum des travaux ")
Sequencement(travaux, 3)

            
                Ce qui suit est la séquence de profit maximum des travaux
                ['c', 'a']
            

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :