Exercice similaire au problème du sac à dos

Bonjour, j'ai actuellement créé une fonction qui renvoie une liste sous cette forme : [ (id_élément1, poids1, temps1) , (id_élément2, poids2, temps2) , etc ].

Maintenant j'aimerais créer une autre fonction qui prend en paramètre un temps et qui renvoie une nouvelle liste qui contient des éléments dont la somme des poids est maximale sachant que la somme des temps de tous ces éléments de cette nouvelle liste ne doit pas dépasser le temps qu'on a entré en paramètre.

Exemple : Soit la liste obtenu : [ (élément1, 2, 10) , (élément2, 5, 7) , (élément3, 9, 15) , (élément4, 7, 11) ].

On entre en paramètre le temps qui vaut 23 par exemple.

La fonction doit donc renvoyer dans ce cas la liste : [ élément2, élément3 ] car la somme de leur temps est égale à 7 + 15 = 22 ce qui est bien inférieur à 23 et la somme de leur poids ( 5 + 9 = 14) est maximale en respectant le temps.

Voilà si quelqu'un pouvait m'aider ou me donner quelques pistes de recherche ça serait sympa. Je précise que je peux avoir accès à tous les informations poids/temps de la liste, mon problème étant juste de trouver une méthode pour maximiser le poids en respectant la contrainte de temps.

Je vous remercie de votre réponse !

Bonjour :coucou:

Chaque élément de ta liste a une pente. En effet pour chaque unité de temps, on gagne un certain poids. Tu cherches donc la pente moyenne la plus forte. Pourquoi ne pas calculer pour chaque élément ? Et comme tu vas tester tous les cas possibles, commencer par les pentes les plus fortes.

Ceci te permettra, à chaque étape, de couper en deux l'ensemble des morceaux restant : acceptables ou réfutés.

Merci pour ta réponse Flodelarab ! En faite j'ai déjà fait un algo permettant de trouver une solution approchée :
1) J'ai commencé par classer les objets dans une liste par ordre décroissant de leur rapport poids/temps.
2) Puis en parcourant cette liste je rajoute au fur et à mesure les objets tant qu'il reste de la place.

Le problème c'est que cette méthode permet seulement de trouver une solution approchée et pas toujours optimal.
Je voudrais donc savoir s'il existe une méthode permettant de trouver la solution optimal mais en restant dans un temps de résolution raisonnable et non exponentielle car j'ai beaucoup d'objet à prendre en compte.

Merci !

Pourquoi "pas en temps exponentiel" ? Le sac à dos ou le voyageur de commerce sont des problèmes simples : il existe des instances particulières sur lesquelles il est difficile de trouver une solution optimale "rapidement" (c'est-à-dire en temps polynomial), mais on peut résoudre une énorme majorité des instances utiles en pratique bien assez rapidement (ce n'est pas toujours le cas pour leurs variantes, hein :aie:). L'exponentielle n'est valable que dans le pire cas, bien souvent.

Bonjour Dourouc05, pourquoi pas en temps exponentiel ? C'est parce que j'étudie beaucoup d'objet en même temps (par exemple 100) et donc si c'est en temps exponentiel je pense que le temps de calcul sera très très long :( Donc voilà pourquoi je pense à rester dans une solution approchée vu que trouver une solution optimale dans un temps polynomial n'est pas encore possible actuellement et que personne n'a encore réussi à faire ça d'après mes recherches.

salut

qu'entend tu par optimal ?
la solution du remplissage à l'aide des éléments triés du plus grand au plus petit est optimal.
Le fait que tout soit à posteriori distribué équitablement est l'un des but recherché non ?
je m'explique

imaginons que tu ai 5 (10,15,5,1,20) valeurs et 3 sacs
tu doit les remplir

1) On trie les valeurs => (20,15,10,5,1)

la première solution serais de remplir jusqu’à obtention de la valeur voulue et de passer au sac suivant
imaginons que la valeur a obtenir soit 25

on boucle tans que la somme de valeur et inférieur ou égale on ajoute

Citation:

---

S1 = 20,5

---

on boucle tans que la somme de valeur et inférieur ou égale on ajoute

Citation:

---

S2= 15,10
S3=1

---

une autre solution serait
on remplit chaque sacs simultanément ce qui nous donnerai
1°) Boucle

Citation:

---

S1 = 20
S2 = 15
S3 = 10

---

2°) Boucle en inversant l'ordre des sacs triés par valeur croissante (l'inverse des valeurs restant a attribuer)

Citation:

---

S1 = 20 ...
S2 = 15,1 (2° choix)
S3 = 10,5 (1° choix)

---

tout dépend du but a atteindre est ce une meilleur répartition ou un max de sac rempli que tu veut obtenir

Il manque aussi les ordres de grandeurs de tes valeurs. Car, si laisser une place vide est gravissime par rapport à combler cette place avec un élément médiocre, alors ton choix ne doit pas forcément se reporter sur la pente maximale mais sur un remplissage complet du temps.

En effet, ton algorithme n'est pas optimal si un élément de grande pente exclut une meilleure solution avec des éléments de pente inférieure.

anapurna voici un exemple qui montre que la méthode dit "gloutonne" n'est pas optimal :

On considère un sac de capacité W = 15 et le n-uplet d'objets S = ((9,10), (12,7), (2,1), (7,3), (5,2)). ((poids1,valeur1) ... (poids5,valeur5))

En triant par ordre décroissant de leur rapport valeur/poids, on a la liste : (1.11 , 0.58 , 0.5 , 0.43 , 0.4) à deux décimales près.

Donc avec la méthode utilisée ici, on choisirait le 1er objet puis le 3ème pour une valeur totale de 11, alors que la solution optimale est constituée du 1er objet et du dernier objet, pour une valeur totale de 12.


Oui Flodelarab il faut que je comble les espaces vides restants quitte à mettre un élément médiocre c'est pour ça que mon algorithme n'est pas optimal comme tu l'as dit :)

salut

S = ((9,10), (12,7), (2,1), (7,3), (5,2))

trie sur la valeur
=> (12,7),(9,2),(7,3),(5,2),(2,1)

Citation:

---

S1 = 12
S2 = 9+5
S3 = 7+2

---

c'est ce que je dis tout dépend de tes critères et du but a attendre
dans ce cas la c'est le premier choix tu remplis sac par sac jusqu’à obtention de ta valeur ... les sacs ne seront pas forcement equilibré
mais remplit le plus possible

Citation:

---

Envoyé par HugoTrn

Bonjour Dourouc05, pourquoi pas en temps exponentiel ?

---

Ce que tu n'as pas compris, c'est que la complexité exponentielle n'est valable que dans le pire cas, sauf dans le cas de problèmes très ardus (par exemple, quand calculer une approximation à epsilon près reste dans la classe de complexité NPH). Parfois, d'ailleurs, un algorithme de complexité exponentielle dans le pire cas est beaucoup plus utile qu'un algorithme polynomial (exemple : le simplexe par rapport à la méthode de l'ellipsoïde).

Facile,

Code:

---

1 2 3 4

Pour chaque combinaison C de ta liste Si C respecte la condition Tmax Si C est une meilleure solution Mémoriser C

---

maintenant tu achètes un gros PC et tu parallélises le calcul :D

Ah zut, j'ai raté ce sujet. Bon, j'imagine que ma réponse arrive trop tard, mais bon, je la met par principe.
Tu as toi-même dit que c'était comme le problème du sac à dos (en remplaçant la valeur par le poids, et le poids par le temps). La résolution de ce problème (exacte et efficace) se fait par le principe de la programmation dynamique. Cela est détaillé sur wikipédia sur la page du pb du sac à dos ou plus en détail sur la page de la programmation dynamique.

Citation:

---

Envoyé par AbsoluteLogic

La résolution de ce problème (exacte et efficace) se fait par le principe de la programmation dynamique

---

Pour fignoler, vu que ces notions semblent importantes pour celui qui a posé la question : ce n'est pas un algorithme polynomial, donc pas "efficace" pour les théoriciens (mais plus qu'assez en pratique).