Discussion :

[HugoTrn]

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 !

[Flodelarab]

Bonjour

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.

[HugoTrn]

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 !

[dourouc05]

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 ). L'exponentielle n'est valable que dans le pire cas, bien souvent.

[HugoTrn]

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.

[anapurna]

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

S1 = 20,5

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

S2= 15,10
S3=1

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

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)

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

[Flodelarab]

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.

[dourouc05]

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).