Concours CPGE 2025 - Mines Ponts - Épreuve d’Informatique - Filières MP PC PSI - Autour du sac à dos

Introduction

Le problème du sac à dos, noté également KP (knapsack problem), est un problème d’optimisation combinatoire. Il modélise une situation analogue à celle du remplissage d’un sac à dos ne pouvant pas supporter plus d’un certain poids, avec tout ou partie d’un ensemble donné d’objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale (le profit), avec la contrainte de ne pas dépasser le poids maximum admissible (la quantité totale de ressources disponibles).

Dans le problème du sac à dos multidimensionnel, noté MKP, on considère plusieurs sacs à dos ayant chacun un poids maximum admissible. L’objectif est alors de maximiser la valeur totale des objets contenus dans l’ensemble des sacs à dos.

Les applications pratiques sont nombreuses : transport de marchandises, découpe de matériaux, gestion de portefeuilles financiers, allocation de tâches à des systèmes multiprocesseurs, ...

1 - Base de données - Exemple de fret maritime de conteneurs

2 - Structure de données pour l’espace des objets

3 - Structure de données pour l’espace des solutions

4 - Résolution approchée par un algorithme glouton