Corrigé Mines-Ponts 2025 Informatique commune MP-PC-PSI — Partie 5 (Q12 à Q14) : Programmation dynamique : tableau des profits maximaux et reconstruction

Principe. Pour $k\in [[0,n]]$ et $r\in [[0,b]]$, $P_{\max }(k,r)$ est le profit maximal réalisable avec les objets d'indices $0$ à $k-1$ et au plus $r$ ressources ; $P_{\max }(0,r)=0$ et l'on admet, pour $i\in [[0,n-1]]$ :

$$P_{\max }(i+1,r)=\max \left\{P_{\max }(i,r),P_{\max }(i,r-r_i)+p_i\right\}.$$

Code. KPprogDynamique(obj, b) crée (lignes 2 à 8) une liste de listes T de $n+1$ lignes de $b+1$ zéros ; puis, pour i de $0$ à $n-1$ et r de $0$ à $b$, elle pose T[i+1][r] $=$ max(T[i][r], T[i][r-obj[i][0]]+obj[i][1]) si obj[i][0]<=r, et T[i+1][r] $=$ T[i][r] sinon ; elle renvoie T[n][b].

Une seconde version conserve ces lignes et ajoute la reconstruction : S=n*[0], k=n-1, r=b ; tant que r>0 and k>=0 and T[k+1][r]!=0 (ligne 8) : tant que k>0 and T[k+1][r]==T[k][r], on décrémente k ; puis S[k]=1, r=r-obj[k][0], k-=1. Elle renvoie S, T[n][b].

Q12. Pour obj=[(2,3),(1,4),(4,4)] et $b=5$ : donner T après les lignes 2 à 8, puis T[i+1] à la fin de chaque tour de la boucle sur i ; que renvoie la fonction, et que représente cette valeur ?
Q13. Déterminer, en la justifiant, la complexité temporelle de KPprogDynamique.
Q14. Donner S, k et r après chaque tour de la boucle de reconstruction ; la complexité est-elle modifiée ?