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

Question

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.

cs_jfrancois · Answer

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

cs_Fabien08 · Answer

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.

mulevia · Answer

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

cs_Fabien08 · Answer

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

mulevia · Answer

g essayé de cliquer sur ton lien il ne marche pas malheureusement peux tu le verifier stp

cs_Fabien08 · Answer

Clic droit, enregistrer sous

mulevia · Answer

c bon g trouvé le document en tapant sur google merci

mulevia · Answer

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

cs_Fabien08 · Answer

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.

cs_Fabien08 · Answer

Petite erreur, le nombre de fois que l'on peut choisir une variable a mettre dans le sac.

cs_Fabien08 · Answer

Si tu as du temps, essaies de regarder celui la : www.info.univ-angers.fr/~barichar/page_perso/publications/2002/barichard_hao-JNPC2002.pdf

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

11 réponses

Votre réponse

Discussions similaires