Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Problème avec les graphes
J'ai un problème à résoudre proche de la problématique du remplissage de volume (pb de recursivité). Je garde l'image du volumes et des bouteilles pour le décrire.
J'ai ici 3 volumes à remplir (3 volumes différents) avec 27 bouteilles (de contenances différentes) et je cherche les meilleures façon de remplir les 3 volumes avec les 27 bouteilles (sachant que je peux légèrement dépasser les volumes ~5%).
Comment aborderiez vous le pb?
Merci
Sylvain
Bonjour,
Comme c'est urgent, je commencerais par prendre mon temps.
Puis, en espérant que les bouteilles contiennent du Ricard, je boirais un, deux, ..., apéros, jusqu'à ce que toutes les bouteilles soient vides (j'appellerais du monde en renfort !), puis je mettrais les bouteilles à la poubelle (spéciale "verre", la poubelle).
Plus sérieux, personne ne fera tes devoirs à ta place, donc montre-nous où tu en es de tes réflexions, codage..., et on t'aidera, dans la mesure du possible
As-tu déjà vu les graphes en cours ?
Si oui, ce problème peut se modéliser en les utilisant et la meilleure solution consiste simplement à chercher un chemin minimal.
Après, la difficulté est de créer le graphe à la volée
Bonjour,
la solution bestiale:
une bouteille peut-être dans le Volume 1, le volume 2, le volume 3 ou ne pas être versée du tout : donc 27 puisance 4 possibilités (environ 500000), ce qui peut se traiter sans problème de temps.
Pour chaque possibilité, on calcule le total du liquide dans 1, 2 et 3.
Si il y a un dépassement dans l'un des volumes, on élimine, sinon on compare le total 1+2+3 au meilleur total (sans dépassement) obtenu jusqu'à là.
La récursivité n'est pas vraiment utile pour implémenter cette solution.
D'après mois ça fait plutôt 4 puissance 27 (en fait 3 puissance 27 car j'utilise toutes les bouteilles). Et là, la methode bestiale pose un pb de temps.Envoyé par Graffito
Bonjour,
la solution bestiale
une bouteille peut-être dans le Volume 1, le volume 2, le volume 3 ou ne pas être versée du tout : donc 27 puisance 4 possibilités (environ 500000), ce qui peut se traiter sans problème de temps.
Pour chaque possibilité, on calcule le total du liquide dans 1, 2 et 3.
Si il y a un dépassement dans l'un des volumes, on élimine, sinon on compare le total 1+2+3 au meilleur total (sans dépassement) obtenu jusqu'à là.
La récursivité n'est pas vraiment utile pour implémenter cette solution.
En effet, Kolossal erreur4 puissance 27 !
ouais j'ai vu les graphes...As-tu déjà vu les graphes en cours ?
Si oui, ce problème peut se modéliser en les utilisant et la meilleure solution consiste simplement à chercher un chemin minimal.
Après, la difficulté est de créer le graphe à la volée
Là je ne vois pas comment traiter ce pb sur le mode chemin minimal, puisque j'ai des containtes qui sont mes 3 volumes...
Je te donne un exemple, tu as deux bouteilles de 3 et 7 litres et tu souhaites obtenir le volume 5.
Tu pars au début d'un sommet (c'est un couple) (0,0) qui correspond au deux bouteilles vide (0 pour la contenance). Tu traces des arcs vers d'autre couple (3,0) et (0,5) pour les opérations que tu peux faire à ce stade (c'est à dire remplir le premier ou remplir le second).
Ensuite, à partir de (3,0) tu as : (3,5) ou (0,3) (on verse dans l'autre) ou (0,0) (tu peux vider le premier bidon)
de : (0,5) -> (3,2) ou (3,5) ou (0,0)
etc.. Un moment, tu vas boucler.
Et au final, tu vas avoir un graphe.
Tu prend tous les sommets qui contiennent un 5 dans le couple et tu lances un parcours pour chercher le minimum de tous les chemins minimaux vers ces sommets. en partant de (0,0)
mais ceci donne une solution exact et optimal, alors que apparement, tu cherches une solution :
(sachant que je peux légèrement dépasser les volumes ~5%).
Désolé, je me suis trompé, erreur d'interprétation du problème.
Bonjour,
Une méthode qui pourrait donner des idées (et éventuellement des résultats) :
- classons les 3 volumes en ordre croissant,
- classons les bouteilles en ordre décroissant de la + grande à la + petite,
- essayons de remplir le volume 1 avec les plus grandes bouteilles (par exemple : 2/3 des bouteilles),
- soit 2 puissance 18 posssibilités à envisager pour 2/3 des bouteilles,
- gardons les N1 meilleures possibilités classées dans l'ordre du plus grand remplissage du volume 1 (sans dépassement),
Pour chacune de ces N1 possibilités :
- compléter au mieux l'espace restant dans le volume 1 avec les peites bouteilles (l'autre 1/3)
- essayons de remplir le volume 2 avec les les plus grandes bouteilles (par exemple : 2/3 des bouteilles) non utilisées pour le volume 1,
- gardons les N2 meilleures possibilités
Pour chacune de ces N2 possibilités :
- compléter au mieux l'espace restant dans le volume 2 avec les petites bouteilles non traitées
- essayons de remplir le volume 3 avec toutes les bouteilles volumes non utilisées pour les volumes 1 et 2,
- si on tombe sur une soluce qui marche, bingo
C'est juste une piste qui ne me satisfait pas totalement.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager