La programmation dynamique (DP) repose sur la décomposition d'un problème complexe en sous-problèmes plus simples, en stockant les résultats pour éviter des calculs redondants. Avant d'aborder le problème du sac à dos, il est essentiel de maîtriser les fondements suivants :

• Cheminement dans une grille : Définir dp[i][j] comme le nombre de chemins uniques pour atteindre la cellule (i, j). L'initialisation des bordures est cruciale, car un obstacle bloque tout chemin ultérieur sur la même ligne ou colonne.
• Décomposition d'entiers : Pour maximiser le produit d'un nombre n décomposé, dp[i] représente le produit maximal pour l'entier i. La transition compare le produit actuel avec j * (i - j) et j * dp[i - j].
• Arbres de recherche binaire (BST) : Le calcul du nombre de structures BST possibles pour n nœuds utilise la relation dp[i] += dp[j - 1] * dp[i - j], où j est le nœud racine.

Le problème classique du sac à dos 0/1 consiste à sélectionner des objets ayant un poids et une valeur spécifiques pour maximiser la valeur totale sans dépasser une capacité W. Chaque objet est unique (disponible une seule fois).

Définition de l'état

Soit memo[i][j] la valeur maximale obtenue en considérant les objets de l'index 0 à i avec une capacité de sac de j.

Relation de récurrence

Pour chaque objet i, nous avons deux choix :

1. Exclure l'objet i : La valeur reste celle obtenue avec les objets précédents : memo[i-1][j].
2. Inclure l'objet i : On ajoute sa valeur à la valeur maximale possible avec la capacité restante : valeur[i] + memo[i-1][j - poids[i]].

L'équationn devient : memo[i][j] = max(memo[i-1][j], memo[i-1][j - poids[i]] + valeur[i]).

public class SolveurSacADos2D {
   public static void main(String[] args) {
       Scanner fluxEntree = new Scanner(System.in);
       int nbArticles = fluxEntree.nextInt();
       int capaciteMax = fluxEntree.nextInt();

       int[] masses = new int[nbArticles];
       int[] prix = new int[nbArticles];

       for (int i = 0; i < nbArticles; i++) masses[i] = fluxEntree.nextInt();
       for (int i = 0; i < nbArticles; i++) prix[i] = fluxEntree.nextInt();

       int[][] matriceDP = new int[nbArticles][capaciteMax + 1];

       // Initialisation pour le premier objet
       for (int c = masses[0]; c <= capaciteMax; c++) {
           matriceDP[0][c] = prix[0];
       }

       // Remplissage de la matrice
       for (int i = 1; i < nbArticles; i++) {
           for (int j = 0; j <= capaciteMax; j++) {
               if (j < masses[i]) {
                   matriceDP[i][j] = matriceDP[i - 1][j];
               } else {
                   matriceDP[i][j] = Math.max(matriceDP[i - 1][j], 
                                            matriceDP[i - 1][j - masses[i]] + prix[i]);
               }
           }
       }
       System.out.println(matriceDP[nbArticles - 1][capaciteMax]);
   }
}
       

Puisque memo[i][j] ne dépend que de la ligne précédente i-1, nous pouvons réduire la complexité spatiale à un tableau unidimensionnel dp[j].

L'importance de l'ordre d'itération

Pour un tableau 1D, il est impératif d'itérer la capacité j de manière décroissante. Cela garantit que chaque objet n'est utilisé qu'une seule fois. Une itération croissante reviendrait à résoudre le problème du sac à dos complet (objets infinis).

public class SolveurSacADosOptimise {
   public void calculerMax() {
       int[] masses = {1, 3, 4};
       int[] valeurs = {15, 20, 30};
       int capaciteSujet = 4;

       int[] tabDP = new int[capaciteSujet + 1];

       for (int i = 0; i < masses.length; i++) { // Parcours des objets
           for (int j = capaciteSujet; j >= masses[i]; j--) { // Parcours inversé de la capacité
               tabDP[j] = Math.max(tabDP[j], tabDP[j - masses[i]] + valeurs[i]);
           }
       }
       System.out.println(tabDP[capaciteSujet]);
   }
}
       

Le problème consiste à déterminer si un tableau d'entiers peut être divisé en deux parties de somme identique. Cela revient à chercher un sous-ensemble dont la somme est exactement SommeTotale / 2.

Modélisation en Sac à dos 0/1

• Capacité du sac : cible = SommeTotale / 2.
• Poids et Valeur : Pour chaque nombre n, son poids est n et sa valeur est n.
• Objectif : Si dp[cible] == cible, alors une partition parfaite existe.

public class PartitionSommeEgale {
   public boolean peutPartitionner(int[] nombres) {
       int total = 0;
       for (int n : nombres) total += n;

       // Si la somme est impaire, impossible de diviser en deux entiers égaux
       if (total % 2 != 0) return false;

       int cible = total / 2;
       int[] memo = new int[cible + 1];

       for (int i = 0; i < nombres.length; i++) {
           for (int j = cible; j >= nombres[i]; j--) {
               memo[j] = Math.max(memo[j], memo[j - nombres[i]] + nombres[i]);
           }
           // Optimisation : arrêt précoce si la cible est atteinte
           if (memo[cible] == cible) return true;
       }

       return memo[cible] == cible;
   }
}
       

Cette approche garantit une complexité temporelle de O(n * cible) et une complexité spatiale optimisée de O(cible).