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
Considérer les travaux suivants :
| Travail | Date limite | Bénéfice |
|---|---|---|
| a | 4 | 20 |
| b | 1 | 10 |
| c | 1 | 40 |
| d | 1 | 30 |
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. Pour chaque travail 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, ignorez le travail en cours.#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
char nom;
int deadline;
int profit;
} Travail;
int comparer(const void* a, const void* b) {
return ((Travail*)b)->profit - ((Travail*)a)->profit;
}
void sequencement(Travail travaux[], int n, int creneaux) {
// Trier les travaux par profit décroissant
qsort(travaux, n, sizeof(Travail), comparer);
// Créneaux disponibles
bool* resultat = calloc(creneaux, sizeof(bool));
// Résultat
char jobs[creneaux];
int nbJobs = 0;
// Pour chaque travail
for (int i = 0; i < n; i++) {
// Trouver un créneau disponible avant la deadline
for (int j = (creneaux < travaux[i].deadline ? creneaux - 1 : travaux[i].deadline - 1); j >= 0; j--) {
if (!resultat[j]) {
resultat[j] = true;
jobs[nbJobs++] = travaux[i].nom;
break;
}
}
}
// Afficher le résultat
printf("Séquence de profit maximum des travaux : ");
for (int i = 0; i < nbJobs; i++) {
printf("%c ", jobs[i]);
}
printf("\n");
free(resultat);
}
int main() {
Travail travaux[] = {
{'a', 4, 20},
{'b', 1, 10},
{'c', 1, 40},
{'d', 1, 30}
};
int n = sizeof(travaux) / sizeof(travaux[0]);
printf("Ce qui suit est la séquence de profit maximum des travaux :\n");
sequencement(travaux, n, 3);
return 0;
}# 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) Sortie Python
Ce qui suit est la séquence de profit maximum des travaux ['c', 'a']
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.