Discussion :

[poof65]

Bonsoir developpeur, developpeuses.

Alors voilà je travaille sur la résolution du problème de sac à dos à l'aide de la programmation dynamique.
J'ai trouvé l'algorithme classique sur wikipedia (http://fr.wikipedia.org/wiki/Probl%C...tion_dynamique) et je l'ai implémenté.

Cependant j'aimerais l'optimiser en réduisant la consommation mémoire en O(n+W), n étant le nombre d'objets et W la capacité du sac (c'est aussi sur la page wikipedia que j'ai entendu parler de cette optimisation).
J'ai réfléchi a peu près deux jours sur ce problème sans rien trouver puis googlé deux autres jours toujours sans succès.

Ma question est simple, connaissez vous cet algorithme qui n'utilise que deux tableaux à une dimension, qui peut calculer le gain optimal et retrouver les objets utilisés pour atteindre ce gain ?

Dernière chose, l'optimisation mémoire en O(W) ne m'intéresse pas car je dois retrouver les objets mis dans le sac une fois le gain maximal calculé.

Merci.

[FrancisSourd]

Tu peux regarder ce livre téléchargeable (chaptre 2.6 surtout)
mais je ne suis pas sûr qu'il y a la réponse.
http://www.or.deis.unibo.it/knapsack.html

[YéTeeh]

Bonjour,

Le livre "Knapsack Problems" de Kellerer et al. (http://www.diku.dk/knapsack/) présente à peu près tout ce qui a été fait sur le problème du sac à dos jusqu'à 2004. En particulier, il présente un algo pour résoudre une instance par programmation dynamique en O(nc) en temps et O(n+c) en mémoire.

C'est loin d'être simple, je ne sais pas si ça vaut le coup de détailler les 5 pages ici. Par contre je peux te les photocopier et te les envoyer (c'est en anglais).

(dans quelle mesure ça reste légal de copier des pages d'un livre ?)

Voilà quand même l'algo tel que sorti du bouquin, mais sache qu'il y a plusieurs hypothèses à vérifier (le bouquin explique bien qu'elles sont vérifiées pour le problème du sac à dos).

On notera
- N un (sous) ensemble des éléments,
- C une capacité,
- X*(N,C) une solution optimale pour cette instance,
- z*(N,C) la valeur de X*(N,C)
- SOLVE(N, C) est un algo qui calcule z*(N,c) pour tout c dans {0,...,C} en O(|N|*C) temps et O(|N|+C) en mémoire (je crois que tu as déjà un tel algo), et si |N|=1, alors il calcule aussi X*(N,C).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
-- Algorithme Recursive-DP(N,C) --
 
Partitionner N en deux ensembles disjoints N1 et N2 de taille équivalentes
Appeler SOLVE(N1, C) pour obtenir z*(N1, c) pour tout c dans {0,...,C}
Appeler SOLVE(N2, C) pour obtenir z*(N2, c) pour tout c dans {0,...,C}
Trouver C1, C2 tels que C1+C2=C et z*(N1,C1)+z*(N2,C2) = z*(N,C)
 
si |N1| = 1 alors
  fusionner X*(N1,C1) et X*(N*,C*) en X*(union(N1,N*), C1+C*)
  N* = union(N*,N1)
  C* = C* + C1
fin si
 
si |N2| = 1 alors
  fusionner X*(N2,C2) et X*(N*,C*) en X*(union(N2,N*), C2+C*)
  N* = union(N*,N2)
  C* = C* + C2
fin si
 
si |N1| > 1 alors appeler Recursive-DP(N1,C1)
si |N2| > 1 alors appeler Recursive-DP(N2,C2)

[poof65]

Tout d'abord merci Francis et YéTeeh pour vos réponses.

YéTeeh> Je vais essayer de comprendre l'algorithme que tu as donné mais ça m'intéresserais aussi d'avoir les 5 pages du livre concernant cette solution (tu voulais dire scanner au lieu de photocopier ?).

Edit: je vois a peu près comment fonctionne ton algo, il procède récursivement en découpant a chaque fois le problème en deux et il calcule l'optimum pour ces deux problème et essaie de trouver une combinaison pour arriver à l'optimum du problème parent.

Le truc qui me gène c'est que ça me parait très couteux en terme de complexité (en temps). Déjà le premier appel de Recursive-DP, calcule z*(N1, c), z*(N2, c) et z*(N, c) grâce à SOLVE qui est en O(|N|*C).
Et comme SOLVE est rappelé 2 fois à chaque recursion ça donne une complexité en O(log(|N|) * |N| * C).

Me serait-je trompé quelque part dans mon étude de l'algo ?

[poof65]

Bon voilà le problème est résolu, merci YéTeeh.