Problème du sac à dos - Définition

Introduction

Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ?

Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un problème d'optimisation combinatoire. Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum.

Histoire

Dans la recherche

Le problème du sac à dos est l'un des 21 problèmes NP-complets de Richard Karp, exposés dans son article de 1972. Il est intensivement étudié depuis le milieu du XX^e siècle et on trouve des références dès 1897, dans un article de George Ballard Mathews. La formulation du problème est fort simple, mais sa résolution est plus complexe. Les algorithmes existants peuvent résoudre des instances pratiques de taille importante. Cependant, la structure singulière du problème, et le fait qu'il soit présent en tant que sous-problème d'autres problèmes plus généraux, en font un sujet de choix pour la recherche.

Complexité et cryptographie

Ce problème est à la base du premier algorithme de chiffrement asymétrique (ou à « clé publique ») présenté par Martin Hellman, Ralph Merkle et Whitfield Diffie à l'université Stanford en 1976. Toutefois, même si l'idée est due au problème du sac à dos, RSA est considéré comme le premier véritable algorithme de chiffrement asymétrique.

La version NP-difficile de ce problème a été utilisée dans des primitives et des protocoles de cryptographie, tels que le cryptosystème de Merkle-Hellman ou le cryptosystème de Chor-Rivest. Leur avantage par rapport aux cryptosystèmes asymétriques fondés sur la difficulté de factoriser est leur rapidité de chiffrement et de déchiffrement. Cependant, l'algorithme de Hellman, Merkle et Diffie est sujet aux « portes dérobées » algorithmiques, ce qui implique qu'il est « cassé », c'est-à-dire cryptanalysé. Le problème du sac à dos est un exemple classique de méprise en ce qui concerne les liens entre la NP-complétude et la cryptographie. Une version revue de l'algorithme, avec une itération du problème du sac à dos, a alors été présentée, pour être sitôt cassée. Les algorithmes de chiffrement asymétrique fondés sur le sac à dos ont tous été cassés à ce jour, le dernier en date étant celui de Chor-Rivest.

Autres domaines concernés

On l'utilise aussi pour modéliser les situations suivantes, quelquefois en tant que sous-problème :

• dans des systèmes d'aide à la gestion de portefeuille : pour équilibrer sélectivité et diversification dans le but de trouver le meilleur rapport entre rendement et risque pour un capital placé sur plusieurs actifs financiers (actions...) ;
• dans le chargement de bateau ou d'avion : tous les bagages à destination doivent être amenés, sans être en surcharge ;
• dans la découpe de matériaux : pour minimiser les chutes lors de la découpe de sections de longueurs diverses dans des barres en fer.

Une autre raison de s'intéresser à ce problème est son apparition dans certaines utilisations de méthodes de génération de colonnes (ainsi pour le problème de « bin packing »).

Anecdotiquement et justifiant ainsi le nom du problème, un randonneur y est confronté au moment de préparer son périple : le sac à dos a une capacité limitée et il faut donc trancher entre prendre, par exemple, deux boîtes de conserve et une gourde de cinquante centilitres ou une seule boîte de conserve et une gourde d'un litre.