Concepts fondamentaux de la programmation dynamique

La programmation dynamique (DP) résout des problèmes d'optimisation et de dénombrement en décomposant les problèmes complexes en sous-problèmes. Elle s'applique depuis les niveaux débutants jusqu'aux compétisions avancées.

Propriétés des problèmes résolubles par DP

Sous-structure optimale

La solution optimale du problème global dépend de solutions optimales de sous-problèmes indépendants. La combinaison de ces solutions partielles produit le résultat final.

Absance de rétroaction

La résolution d'un sous-problème est indépendante des étapes ultérieures. Une fois calculée, sa valeur reste inchangée quelle que soit l'évolution des calculs.

Méthodologie de résolution

1. Décomposer le problème en sous-problèmes
2. Définir les états du système
3. Initialiser les états de base
4. Établir les équations de transition
5. Implémenter la solution par récursion mémoïsée ou itération

Complexité temporelle

Produit du nombre d'états possibles et du coût de chaque transition.

Exemple : Triangle numérique (IOI1994)

Problème classique illustrant les principes de base. Pour un triangle de nombres, trouver le chemin de somme maximale de la base au sommet.

• Sous-structure optimale : La valeur à chaque position dépend des deux cellules supérieures
• Absence de rétroaction : Le calcul à chaque étape est indépendant des chemins antérieurs

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_LIGNES = 1005;
int valeurs[MAX_LIGNES][MAX_LIGNES];
int sommes[MAX_LIGNES][MAX_LIGNES];

int main() {
    int nb_lignes;
    cin >> nb_lignes;
    
    for (int ligne = 1; ligne <= nb_lignes; ligne++) {
        for (int colonne = 1; colonne <= ligne; colonne++) {
            cin >> valeurs[ligne][colonne];
        }
    }
    
    sommes[1][1] = valeurs[1][1];
    
    for (int ligne = 2; ligne <= nb_lignes; ligne++) {
        for (int colonne = 1; colonne <= ligne; colonne++) {
            int gauche = (colonne > 1) ? sommes[ligne-1][colonne-1] : 0;
            int droite = (colonne < ligne) ? sommes[ligne-1][colonne] : 0;
            sommes[ligne][colonne] = max(gauche, droite) + valeurs[ligne][colonne];
        }
    }
    
    int resultat = *max_element(sommes[nb_lignes] + 1, sommes[nb_lignes] + nb_lignes + 1);
    cout << resultat << endl;
    return 0;
}

Problématiques de sac à dos

Sac à dos 0-1

Modèle de base où chaque objet est sélectionné au plus une fois. Exemple : sélection d'objets de valeurs et poids varialbes dans un sac de capacité limitée.

Représentation des états

resultats[i][c] : Valeur maximale obtenable avec les i premiers objets pour une capacité c.

Équation de transition

resultats[i][c] = max(resultats[i-1][c], resultats[i-1][c-poids[i]] + valeur[i])

Optimisation spatiale

Utilisation d'un tableau unidimensionnel avec parcours inversé :

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int capacite, nb_objets;
    cin >> capacite >> nb_objets;
    
    int poids[nb_objets+1], valeur[nb_objets+1];
    for (int i = 1; i <= nb_objets; i++) {
        cin >> poids[i] >> valeur[i];
    }
    
    int dp[capacite+1] = {0};
    
    for (int i = 1; i <= nb_objets; i++) {
        for (int c = capacite; c >= poids[i]; c--) {
            dp[c] = max(dp[c], dp[c - poids[i]] + valeur[i]);
        }
    }
    
    cout << dp[capacite] << endl;
    return 0;
}

Variantes principales

Sac à dos complet

Objets sélectionnables indéfiniment (P1616)

Sac à dos multiple

Objets disponibles en quantités limitées (P1776)

Sac à dos groupé

Sélection par groupes mutuellement exclusifs

Sac à dos mixte

Combinaison des contraintes précédentes (P1833)

Applications avancées

Extensions du modèle classique pour résoudre des problèmes d'optimisation complexes