Scribd
Importer
11 vues2 pages

Programmation dynamique : Problème du sac à dos

Ce document décrit le problème du sac à dos, qui consiste à remplir un sac à dos avec des objets de poids et profits donnés sans dépasser le poids maximal tout en maximisant le profit. Il présente un algorithme de programmation dynamique pseudo-polynomial pour résoudre ce problème NP-complet.

Transféré par

SALAH EDDINE
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
11 vues2 pages

Programmation dynamique : Problème du sac à dos

Ce document décrit le problème du sac à dos, qui consiste à remplir un sac à dos avec des objets de poids et profits donnés sans dépasser le poids maximal tout en maximisant le profit. Il présente un algorithme de programmation dynamique pseudo-polynomial pour résoudre ce problème NP-complet.

Transféré par

SALAH EDDINE
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université d’Aix-Marseille L2 Informatique - 2012/2013

Algorithmique

TP7 : Programmation dynamique – Pb. du sac à dos


Problème On dispose d’un sac à dos dont la charge maximale est Pmax et
d’un ensemble de n objets U = {1, . . . , n} de poids P1 , . . . , Pn et de profits
potentiels V1 , . . . , Vn . L’objectif est de remplir le sac à dos avec un ensemble
d’objets O ⊆ U sans dépasser le poids maximal Pmax tout en maximisant le
profit, i.e. X X
Pi ≤ Pmax et Vi est maximal.
i∈O i∈O

Il y a deux cas :
– le cas trivial qui correspond à celui où tous les objets rentrent dans le sac
sans dépasser Pmax ;
– le cas général, pour lequel il faut choisir parmi les objets de U ceux que
l’on va emporter.
Dans tous les cas le profit est au plus

n × max Vi .
i∈U

Ce problème est NP-complet : on ne connaı̂t pas d’algorithme polynomial pour


le résoudre.
Cependant, il existe un algorithme pseudo-polynomial 1 . On utilise une table de
programmation dynamique A à deux dimensions telle que A(i, p) représente le
profit maximal que l’on peut obtenir en prenant un sous-ensemble d’objets de
{1, . . . , i} dont le poids total est inférieur ou égal à p. A(i, p) vaut 0 s’il n’existe
aucun sous-ensemble de {1, . . . , i} de poids au plus égal à p. Le gain maximal
A(i + 1, p) est défini de la manière suivante
( 
A(i + 1, p) = max A(i, p), A(i, p − Pi+1 ) + Vi+1 si Pi+1 ≤ p
A(i + 1, p) = A(i, p) sinon.

Autrement dit, A(i + 1, p) est obtenu soit sans prendre l’objet i + 1, il vaut donc
A(i, p), soit en ajoutant l’objet i + 1 au meilleur chargement d’objets pris dans
{1, . . . , i} de poids au plus p−Pi+1 (le chargement correspondant est fatalement
inférieur à p).
1. polynomial en le nombre d’entrées n et en le plus grand nombre apparaissant dans ces
entrées.

1
Questions
1. Construisez la table A à partir d’un petit exemple avec 4 objets (réfléchissez
aux dimensions de la table A).
2. Ecrivez une fonction qui calcule le meilleur chargement en utilisant la
méthode décrite ci-dessus. Vous allouerez tout d’abord la table de pro-
grammation dynamique. Ensuite vous calculerez les valeurs de cette ma-
trice.
3. Ajouter à la fonction précédente le calcul du meilleur chargement (notez
qu’il peut y en avoir plusieurs, mais un seul nous intéresse).
Indication : Partir de la valeur de A(i, p) la plus grande (inférieure à
Pmax ), on retrouve les choix effectués en comparant A(i, p) avec A(i −
1, p) : s’ils sont égaux une solution est de ne pas prendre l’objet i, sinon
on doit le prendre nécessairement.

Vous aimerez peut-être aussi