Voila, j'ai un exo a faire en java, il s'agit d'un facteur qui peut porter au max 5 kg, mais on ne sait pas combien de colis il y a à l'avance, le but du jeu est de tranporter le maximum de colis sans dépasser 5 KG et en meme temps limiter le nombres de voyages.
 
Si vous connaissez de la doc, un tut, code etc... cela me serait d'une grande utilité vu que je galere pas mal depuis pas mal de tps dessus
 
Merci d'avance !

s'il ne sait pas ce qu'il doit transporter, ca va être dur ...

non mais ce que je veux dire c'est que par exemple il y a on va dire 150 colis, qui varient entre 10g et 4,5kg, et il faut faire le moins de trajet.
Ce que j'entendais par 'il ne sait pas ce qu'il doit transporter' c'etait plus a realiser avec n colis.
Voila, j'espere avoir ete clair cette fois

Essaye toutes les combinaisons possibles puis, si le facteur est toujours en vie, abats-le.
 
Bon, c'est bien amusant tout ça, mais tu t'es renseigné sur l'algo tout court, en dehors de Java ? Une fois que tu auras la partition, ce sera pas trop dur de la mettre en musique.
 
Que proposes-tu ?
 

hummm ouais j'ai essayé de cherché en dehors du java, je cherche un algo  generique marchant avec n'importe quel langage...Mais bon je ne trouve pas
Niveau musique, attention je suis naze en composition

C'est un dérivé d'un problème très connu en algorithmique qu'on appelle "problème du sac à dos". Ce problème appartient à la classe NP, c'est à dire qu'il n'existe aucun algorithme efficace permettant de la calculer.
 
En gros, t'emmerde meme pas à essayer de trouver des ptites techniques de shaolin pour arriver au bon résultat rapidement, ça ne servira à rien, laisse ça à ceux qui ont bac +8. La seule manière de faire, c'est de tester toutes les solutions et de choisir celle qui est la meilleure.
 
Imagine que t'as 3 objets A, B et C:
tu dois tester tout les cas suivants
A B C
A C B
B A C
B C A
C A B
C B A
et prendre le meilleur cas.
Donc tu dois reflechir à "comment tester tout les cas ?" et "comment connaitre le nombre de voyage d'un cas précis?" et aussi "comment prendre le plus petit de tout les cas?" (le dernier est pas trop dur)
 
Si t'as des questions n'hésite pas.

bah je vais te dire oui meme si ta reponse me parait claire, mais je voulais savoir que pour cet exemple tu as pris 3 objets, mais imagine que tu en a n, tu fais ca comment ?
tu vas pas faire un truc du style :
A B C...N
N..B..C..A..
...
si ? Auquel cas ca sera lent comme algo ?
 
Merci de ta reponse

oui ca sera "lent" mais t'as pas le choix

y'a eu une solution plus élégante postée à ce sujet ... une recherche sur sac à dos devrait donner le bon résultat

Le problème du sac à dos avec des valeurs entières peut etre résolu de manière efficace (en utilisant la programmation dynamique), c'est vrai, mais ici les valeurs ne sont pas entières, le poids peut prendre n'importe quelle valeur réelle, on est bien face à la version Non Polynomiale du problème.
 
Voilà un algo récursif qui permet de le résoudre.
 
La procédure récursive Calcul(i,u) a pour paramètres d'appel, i l'objet pour lequel on doit prendre une décision, et u la capacité disponible restante. Elle considère deux possibilités pour l'objet i l'une pour laquelle il est mis dans le sac (si on ne dépasse pas la capacité restante u), l'autre pour laquelle il n'y est pas mis. La procédure appelle Calcul(i+1, u) et Calcul(i+1, u - p[i]). Ainsi le premier appel de calcul(i, u) est fait avec i = 0 et u égal à la capacité M du sac, les appels successifs feront ensuite augmenter i (et diminuer u) jusqu'à atteindre la valeur n. Le résultat est mémorisé s'il améliore la valeur courante de meilleur.
 
procedure Calcul (i: integer; u: real);
    begin
    if i > n then
        if u < meilleur then
            begin
            for j:= 1 to n do msac[i] := sac[i];
            meilleur := u;
            end;
    else
        begin
        if  p[i] <= u then
            begin
            sac[i] := 1;
            Calcul(i + 1, u - p[i]);
            end;
        sac[i] := 0;
        Calcul(i + 1, u);
        end;
    end;
 
On vérifie sur des exemples que cette procédure donne des résultats assez rapidement pour n < 20. Pour des valeurs plus grandes le temps mis est bien plus long car il croît comme 2 puissance n.  
 
extrait de //www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/main8/node8.html
 
Je rappelle que le problème du sac à dos consiste à essayer de remplir au maximum un sac de taille u, avec des objets de taille p[i]. Le probleme du facteur consiste donc à faire le problème du sac à dos plusieurs fois jusqu'à ce qu'on est plus d'objets.

http://www.edm2.com/0601/backpack.html
Algo rapide pour le backpack problem.

Ouais...
Je suis pas sur qu'un programme en C de 500 lignes bourré d'optimisations soit la bonne solution pour un petit exo à faire en java...

Ce ne sont "que" des exemples servant à illustrer la progression de l'idée et de l'algo hein  
 
Rien n'empêche de suivre la pensée pour réimplémenter la chose en java, ou en Ruby, ou en Lisp

drapeau

 
j'ai implémenté cet algo en java, ca marche sans pb. en revanche il y a une petite erreur (elle est aussi sur la page donnée en lien). le vrai algo est le suivant:

 
en revanche, aussi bien sur ce site que sur d'autres que j'ai parcouru par rapport à cet algo "backpack" il est dit que

 
dans mon cas, la capacité du sac (u dans l'algo précédent) est un entier, et pas réel. je comprends donc, d'après l'assertion précédente, que le backpack est alors solutionnable sans avoir à tester toutes les possibilités
 
j'ai cherché un peu mais sans trop de résultats. est-ce que qqun aurait des infos à ce sujet ?
 
merci d'avance

on pourrait pas utiliser l'algo du simplexe ici ?
(remarque peut etre très conne, j'suis une burne en math mais je me rappelle avoir fait ce genre d'exo en cours d'optimisation quand j'étais encore étudiant)

 
Il me semble que pour pouvoir résoudre le problème sans tester toutes les possibiltés, il faut que la capacité du sac ET le poids des objets soient des entiers.

 
c'est le cas
bon, ca ne me donne pas plus d'infos sur cet aspect-là... à moins que du coup, l'algo porte un autre nom que "backpack". pas trop eu le temps de chercher ces 2 dernieres semaines. mais faut que je m'y remette

Alors dans ce cas oui, tu peux utiliser un solution avec programmation dynamique qui est bien plus rapide que l'algo qui explore toutes les possibilités.

oki. merci pour le conseil il me semblait bien que je pouvais utiliser cette méthode. me reste à trouver suffisamment de documentation et à l'implémenter.
aurais-tu qqes liens par hasard stp ?

J'ai pas d'algo tout fait sous la main.
Tape "programmation dynamique sac dos" dans google, y'a le cours de mon prof d'info Mr Robson et d'autres liens qui en parlent et qui peuvent t'aider.

ok. merci pour le "tip" !