Probleme du sac a dos Avec répétition ou "Knapsack with repetition"

Signaler
Messages postés
7
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
24 juin 2008
-
Messages postés
7
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
24 juin 2008
-
Bonjour et merci de vous intéressez à ce sujet. Je dois réaliser une application d'optimisation me permettant d'obtenir la meilleure combinaison de choix par rapport à deux critères.

Après différentes recherche, l'algorithme du "Knapsack with repetition" s'impose comme "la" solution.

Malheureusement impossible de trouver cet algorithme sous forme de pseudo code ou avec une description suffisamment compréhensive pour que je puisse l'implémenter

D'où ma question ; quelqu'un pourrait il me donner une description succincte et suffisamment clair ?
un simple oui serait déjà un bon début.

La seule référence trouvé à ce jour correspond à un article de Timothy J Rofle, An alternative Dynamic Programming Solution for 0/1 Knapsack.

Il aborde vaguement le sujet, ou du moins la présentation qu'il en fait reste très vague pour mon modeste anglais.

Merci bien.
A voir également:

11 réponses

Messages postés
482
Date d'inscription
vendredi 26 août 2005
Statut
Membre
Dernière intervention
5 décembre 2009

Bonjour,

Je viens de trouver ça via Google : http://kiroukou.media-box.net/blog/mes-recherches-sur-flash/9-algo-du-sac-a-dos.html
C'est pas du pseudo-code mais ça peut servir.

Jean-François
Messages postés
7
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
24 juin 2008

Merci beaucoup pour cette réponse mais malheureusement cette algorithme correspond au "Knapsack without repetition", en bref il ne permet pas d'utiliser plusieurs fois le même objet lors de l'optimisation.

Cette optimisation semble relativement simple dans l'immédiat mais elle se complique lorsque l'on ajoute des critères de préférences.

Ce qu'il me faut c'est un algorithme de maximisation, tel le simplex avec la possibilité de n'avoir que des variables entières comme critère de choix.

Voici un cours provenant de l'école polytechnique de Lausanne sur l'optimisation et le simplex.
Cf : http://roso.epfl.ch/cours/rosc/automne2007/index.php?content=cours

Ou l'algorithme qui tu m'as envoyé avec possibilité d'utiliser plusieurs fois le même objet soit "Knapsack with repetition" appellé aussi "Integer Knapsack", en tout cas merci pour ton lien, ce fut rapide et surtout très gentil de partager ton temps libre.
Messages postés
4
Date d'inscription
dimanche 24 octobre 2004
Statut
Membre
Dernière intervention
21 juin 2008

je souhaiterais avoir des liens parlant des différentes variantes de l'algo sac à dos sachant q'un objet peut être choisi une fois, plusieurs fois ou aucune fois
Messages postés
7
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
24 juin 2008

Mon problème est résolu, j'ai travaillé mon anglais et miracle la solution était dans l'article : Sinon pour le lien :

[penguin.ewu.edu/%7Etrolfe/Knapsack01/Knapsack01.doc penguin.ewu.edu/~trolfe/Knapsack01/Knapsack01.doc]

Wikipédia fournit aussi quelques infos. Malheureusement, on se borne uniquement à une seule contrainte et ça limite un peu les choix.

Le problème vient non linéarité du problème.

Accessoirement :
une seule fois : Knapsack without repetition ou 0/1 Knapsack
plusieurs fois : Knapsack with repetition ou Integer Knapsack
Aucune fois : Ne simplement pas inclure ta valeur 
Messages postés
4
Date d'inscription
dimanche 24 octobre 2004
Statut
Membre
Dernière intervention
21 juin 2008

g essayé de cliquer sur ton lien il ne marche pas malheureusement peux tu le verifier stp
Messages postés
7
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
24 juin 2008

Clic droit, enregistrer sous
Messages postés
4
Date d'inscription
dimanche 24 octobre 2004
Statut
Membre
Dernière intervention
21 juin 2008

c bon g trouvé le document en tapant sur google merci
Messages postés
4
Date d'inscription
dimanche 24 octobre 2004
Statut
Membre
Dernière intervention
21 juin 2008

o fait j'ai bien cerné l'algo de knapsack sans repetition mais celui avec repetition, j n'arive pa trop bien à le comprendre.je vous renvoie l'algo
K

(0) = 0for

w = 1 to W:K

(w) = max{K(w-wi) + vi : wi<=w}return

K(W)

je n'arrive pas tro bien à comprendre ce qu'on compare après le max
Messages postés
7
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
24 juin 2008

Alors ce que tu m'as envoyé ne correspond pas à l'algo entier, c'est juste une partie de la présentation. Si tu lis les lignes suivantes tu verras qu'il se sert de cette partie pour formuler le résultat qu'il présente sous forme de code en Java.

Sinon :
le w sans indice correspond à l'indice de la boucle for.

le wi correspond au vecteur contenant la largeur de l'objet à placer dans le sac

le vi correspond au cout
Finalement tu dois avoir une première boucle qui te permet d'avoir l'indice i, elle n'est pas présenté dans le pseudo code, et une condition après la seconde boucle : if wi <w then ... K(w) ... end_if

Mais lorsque tu lis l'article tu comprends que ce n'est pas la solution présenté, elle se trouve dans le code en java.

Si tu t'interresses aux Knapsacks, j'aimerais ,si tu en as avoir, des infos sur le Bound Knapsack, c'est la version avec répétition mais bornée, elle limite le nombre de valeur a mettre dans le sac.
Messages postés
7
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
24 juin 2008

Petite erreur, le nombre de fois que l'on peut choisir une variable a mettre dans le sac.
Messages postés
7
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
24 juin 2008

Si tu as du temps, essaies de regarder celui la :

www.info.univ-angers.fr/~barichar/<wbr>page_perso/publications/2002/barichard_hao-JNPC2002.pdf

</wbr>