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

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.

Bonjour,

Je viens de trouver ça via Google : [ Lien ]
C'est pas du pseudo-code mais ça peut servir.

Jean-François

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 : [ Lien ]

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.

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

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/~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 

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

Clic droit, enregistrer sous

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

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) = 0

for 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

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.