2025 Mines Info commune MP PC PSI — Corrigé

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).

D’un point de vue mathématique, la formulation du problème du sac à dos est la suivante : Maximiser le profit total {P=\sum\limits_{i=0}^{n-1}p_ix_i} sous la contrainte {\sum\limits_{i=0}^{n-1}r_ix_i\le b} où

  • {n} est le nombre d’objets candidats,

  • {i} est l’entier caractérisant l’objet ({i\in\{0,\ldots,n-1\}}),

  • {p_i} est le profit (ou valeur) associé à l’objet {i},

  • {x_i} est la variable de décision associée à l’objet {i} : {x_i=1} si l’objet {i} est sélectionné et {x_i=0} sinon,

  • {r_i} est la quantité de ressources consommée par l’objet {i} (ou poids de l’objet {i}),

  • {b} est la quantité totale de ressources disponibles (ou poids total).

On ne considère que des cas où chaque ressource {r_i}, chaque profit {p_i} et la quantité de ressources disponibles {b}, sont des entiers.

On fait aussi l’hypothèse que {\forall i\in\{0,\ldots,n-1\},\ r_i\le b}.

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

On donne les tables NAVIRES et CONTENEURS suivantes : NAVIRES(idN,evp,portDepN,dateDep,portDestN) idN : clé primaire, identifiant du navire (type entier, non nul) evp : capacité en équivalent conteneurs de longueur 20 pieds (type entier) portDepN : port de départ (type chaîne de caractères) dateDep : date de départ (type date) portDestN : port de destination (type chaîne de caractères)

Figure 1

CONTENEURS(idC,idN,taille,portDepC,dateDisp,portDestC,val) idC : clé primaire, identifiant du conteneur (type entier) idN : identifiant du navire attribué (type entier, valeur 0 si non encore attribué). taille : longueur du conteneur, 20 ou 40 pieds (type entier).

La hauteur et la profon- deur sont identiques. portDepC : port de départ (type chaîne de caractères) dateDisp : date de mise à disposition (type date) portDestC : port de destination (type chaîne de caractères) val : tarification, valeur entière de 1 à 5 par ordre croissant de profit pour l’entreprise (type entier)

Figure 2

Pour les deux questions qui suivent, on demande d’écrire les requêtes en langage SQL.

On notera que pour les valeurs d’attributs de type date (format AAAA-MM-JJ), les relations d’ordre {(\lt,\le,>,\ge,=,\ne)} sont autorisées. Par exemple, 2025-07-02 < 2025-10-03.

Q1. Écrire une requête permettant de retourner la liste des identifiants de conteneurs et leur ratio tarification/longueur trié par ordre décroissant, partant de Marseille et devant aller à Barcelone, avec une mise à disposition avant le 01/01/2025.
Q2. Écrire une requête permettant de retourner les identifiants de navire et leur nombre respectif de conteneurs attribués.

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

On demande d’utiliser exclusivement le langage Python pour toute la suite du sujet. On implémente l’espace des objets {i} ({i\in\{0,\ldots,n-1\}}) avec une structure informatique obj de type liste de taille {n}.

La valeur de obj[i] est un tuple (ri,pi) où ri et pi sont les valeurs respectives des paramètres {r_i} et {p_i} de l’objet {i}.

Par exemple, (10,5) permet de définir pour un objet étiqueté {3} les paramètres {r_3=10} et {p_3=5}.

Une solution au problème du sac à dos {S=[x_0,x_1,\ldots,x_{n-1}]}, est implémentée par une liste Python. On rappelle que {x_i=1} si l’objet {i} est sélectionné et {x_i=0} sinon.

Pour les deux questions qui suivent, la fonction python sum ne sera pas utilisée.

Q3. Écrire une fonction profit(obj:[(int)],S:[int])->int prenant en argument une liste obj et une liste S, et retournant la valeur du profit P.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :