Résolution d'un problème de sac à dos 0/1 à l'aide d'un exemple de programmation dynamique

Quel est le problème du sac à dos ?

Le Problème de sac à dos est un problème classique d'optimisation combinatoire. Un supermarché stocke n paquets (n ≤ 100). Paquet i Chaque paquet a un poids W[i] ≤ 100 et une valeur V[i] ≤ 100. Un voleur ne peut pas transporter un poids supérieur à la capacité M (M ≤ 100). Quels paquets le voleur doit-il emporter pour maximiser la valeur totale ?

Entrées :

• Poids maximum M et nombre de colis n.
• Tableau de poids W[i] et valeur correspondante V[i].

Sortie :

• Valeur totale maximale pouvant être obtenue dans les limites de la capacité.
• La liste exacte des colis que le voleur doit emporter.

L'algorithme du sac à dos se divise en deux variantes bien connues :

• Problème de sac à dos 0/1 Résolu par programmation dynamique. Chaque paquet est soit pris en entier, soit laissé sur place ; pas de fractions ni de doublons.
• Problème de sac à dos fractionnaire Résolu par une stratégie gloutonne. Ici, vous pouvez prendre une fraction de chaque paquet pour remplir la capacité restante.

Comment résoudre le problème du sac à dos à l'aide de la programmation dynamique avec un exemple

La méthode « diviser pour régner » consiste à décomposer un problème complexe en sous-problèmes, puis à poursuivre cette décomposition jusqu'à ce que chaque sous-problème soit simple. Cependant, la récursivité pure résout souvent le même sous-problème à plusieurs reprises, ce qui représente un gaspillage de ressources.

L'idée principale de la programmation dynamique du sac à dos est de stocker chaque sous-problème résolu dans une table. Les appels répétés lisent la réponse au lieu de la recalculer, transformant ainsi une récursion exponentielle en un code à complexité polynomiale.

Résoudre le problème du sac à dos à l'aide de la programmation dynamique

Pour concevoir une solution de programmation dynamique, vous suivez quatre étapes :

• Résolvez d'abord les plus petits sous-problèmes.
• Dériver une récurrence qui construit la solution d'un sous-problème à partir de sous-problèmes plus petits.
• Stockez les réponses aux sous-problèmes dans un tableau calculé de bas en haut en utilisant la récurrence.
• Assemblez la réponse finale à partir du tableau complet.

Analysez le problème du sac à dos 0/1

La valeur optimale dépend de deux facteurs indépendants :

1. Combien de colis sont encore à l'étude ?
2. Le poids restant que le sac à dos peut encore contenir.

Étant donné que la fonction objectif dépend de deux quantités, le tableau des options doit être bidimensionnel. B[i][j] désigne la valeur maximale lors du choix parmi les paquets {1, …, i} avec une limite de poids j.

• La réponse finale est B[n][M], la meilleure valeur totale sur l'ensemble des n paquets sous la capacité M.
• Le poids total sélectionné est toujours limité par la capacité actuelle : B[i][j] ≤ j.

Exemple : si B[4][10] = 8, le meilleur poids total des quatre premiers colis sous la capacité 10 est de 8. Certains de ces quatre colis peuvent être ignorés.

Formule pour calculer B[i][j]

• W[i], V[i] sont le poids et la valeur du paquet i, où i est dans {1, …, n}.
• M est le poids maximal que le sac à dos peut supporter.

Cas de base avec un seul paquet : pour chaque capacité j ≥ W[1] :

B[1][j] = W[1]

Dans le cas général, décidez s'il faut inclure le paquet i dans la capacité j :

• Si le paquet i est sauté, B[i][j] est égal à la meilleure valeur utilisant les paquets {1, …, i-1} sous la capacité j :

B[i][j] = B[i - 1][j]

• Si le paquet i est utilisée (autorisé uniquement lorsque W[i] ≤ j), B[i][j] est égal à V[i] plus la meilleure valeur des paquets {1, …, i-1} sous la capacité j – W[i] :

B[i][j] = V[i] + B[i - 1][j - W[i]]

Choisissez le candidat le plus important des deux.

Base de la programmation dynamique

La combinaison des deux cas donne la récurrence complète :

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Le cas de base est B[0][j] = 0 pour chaque j, car les paquets nuls n'ont aucune valeur, quelle que soit la capacité.

Calculer le tableau des options

Construisez B en utilisant la récurrence. Une fois B rempli, la même table pilote le reste. trace-back qui reconstitue les colis sélectionnés. Le tableau B comporte n + 1 lignes et M + 1 colonnes :

• La ligne 0 correspond au cas de base, rempli de zéros.
• Utilisez la ligne 0 pour calculer la ligne 1, la ligne 1 pour calculer la ligne 2, et continuez jusqu'à ce que la ligne n soit complète.

Tableau des options

Trace

Une fois la phase B terminée, concentrez-vous sur B[n][M], la valeur totale optimale pour l'ensemble des n colis d'une capacité M.

• If B[n][M] = B[n-1][M]Le paquet n n'a pas été sélectionné, veuillez continuer. tracant de B[n-1][M].
• If B[n][M] ≠ B[n-1][M]Le paquet n a été sélectionné, continuez donc tracant de B[n-1][M – W[n]].

Répétez l'opération jusqu'à atteindre la ligne 0 du tableau.

Algorithme pour consulter le tableau des options pour trouver les packages sélectionnés

Remarque : chaque fois que B[i][j] = B[i-1][j]Le paquet i n'est pas sélectionné. La valeur B[n][M] représente la valeur totale optimale contenue dans le sac à dos.

Étapes pour tracen utilisant les forfaits choisis :

• Étape 1 : Commencez à i = n, j = M.
• Étape 2 : Parcourez la colonne j de bas en haut jusqu'à trouver la ligne i où B[i][j] > B[i-1][j]. Marquez le paquet i comme sélectionné. Select[i] = true.
• Étape 3 : Mettre à jour j = j – W[i]. Si j > 0, retourner à l'étape 2, sinon passer à l'étape 4.
• Étape 4 : Imprimer tous les colis marqués comme sélectionnés.

Java Code

Java La méthode remplit B[][] de bas en haut, imprime le tableau pour vérification, puis tracce sont les forfaits sélectionnés.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Fonction sac à dosDyProg() dans Java

Explication du code :

1. Table d'allocation B[][] et initialiser chaque cellule à 0.
2. Remplissez B[][] de bas en haut en utilisant la récurrence de la section précédente.
3. Commencez chaque cellule par la valeur « skip package i ». B[i-1][j].
4. Si le choix du forfait i est possible et offre une valeur strictement meilleure, écrasez la cellule.
5. Trace les éléments sélectionnés de la ligne n jusqu'à la ligne 0.
6. Chaque fois que le paquet n est sélectionné, décrémentez la capacité restante de W[n-1].

Note de correction : le paramètre modifié de l'extrait original M tout en lisant B[n][M]La version plus sûre ci-dessus utilise un curseur séparé. j pour trace.

Le Java Le pilote exécute l'algorithme sur deux exemples fonctionnels :

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Résultat du premier exemple :

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Résultat du deuxième exemple :

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Complexité temporelle et spatiale du sac à dos 0/1

• Complexité temporelle : O(n · M) — les deux boucles imbriquées parcourent n éléments à travers M+1 états de capacité.
• Complexité spatiale : O(n · M) pour le tableau complet, réductible à O(M) par keeping seulement la ligne précédente lorsque tracLe retour électronique n'est pas nécessaire.

La durée d'exécution est pseudo-polynôme: polynomial en la valeur de M mais exponentiel en fonction du nombre de bits utilisés pour coder M. C'est pourquoi le problème du sac à dos 0/1 reste NP-difficile même si la programmation dynamique est efficace en pratique.

Applications du problème du sac à dos 0/1

• Chargement de marchandises, emballage de conteneurs et préparation de commandes en entrepôt dans le respect des limites de poids.
• Répartition du budget entre les projets d'investissement à coûts fixes et à rendement attendu.
• Problèmes de découpe dans la fabrication qui empêchent le fractionnement en pièces individuelles.
• Les schémas de cryptographie tels que Merkle-Hellman qui s'appuient sur la difficulté du sac à dos.
• Planification des ressources limitées dans le cloud computing et placement des tâches CPU.
• Sélection de caractéristiques en apprentissage automatique avec un budget de caractéristiques fixe.

FAQ