Chapitre 17. Le problème du sac à dos

Le problème du couplage parfait de poids minimum et le problème d’intersection de matroïdes avec poids présentés aux chapitres précédents font partie des problèmes les plus « difficiles » pour lesquels on connaît un algorithme polynomial. Dans ce chapitre, nous traitons le problème suivant qui se révèle être, en un certain sens, le plus « facile » des problèmes NP-difficiles :
Les applications correspondent aux situations où l’on veut sélectionner un sous-ensemble optimal, de poids total borné, d’un ensemble d’éléments ayant chacun un poids et un profit associés.
Nous commençons par étudier la version fractionnaire de ce problème au paragraphe 17.1, qui se révèle être résoluble en temps linéaire. Le problème du sac à dos en nombres entiers est NP-difficile comme nous le montrerons au paragraphe 17.2, mais un algorithme pseudo-polynomial le résout optimalement. Nous montrerons au paragraphe 17.3 que cet algorithme combiné à une technique d’arrondi peut être utilisé pour concevoir un schéma d’approximation entièrement polynomial. Nous présenterons au paragraphe 17.4 une généralisation de ce problème dans le cas multidimensionnel.
Nous considérons le problème suivant :L’observation suivante suggère un algorithme simple qui nécessite de trier les éléments de manière appropriée :Proposition 17.1. (Dantzig [1957]) Soient c1, … , cn, w1, … , wn et W des entiers non négatifs tels que , etet soitAlors une solution optimale de l’instance considérée du problème du sac à dos fractionnair…