dynamic-programming
Problème de sac à dos

Remarques

0-1 problème de sac à dos

Supposons qu'on vous demande, compte tenu du poids total que vous pouvez porter sur votre sac à dos et de certains articles avec leur poids et leurs valeurs, comment les prendre de telle sorte que la somme de leurs valeurs soit maximale, mais la somme de leurs poids ne dépasse pas le poids total que vous pouvez transporter? Le 0-1 indique que vous choisissez l'article ou que vous ne le faites pas. Nous avons aussi une quantité de chaque article. Cela signifie que vous ne pouvez pas diviser l'élément. Si ce n'était pas un problème de sac à dos 0-1 , cela signifie que si vous pouviez diviser les éléments, il y a une solution gourmande, appelée problème de sac à dos fractionnaire .

Pour l'instant, concentrons-nous sur notre problème actuel. Par exemple, disons que nous avons une capacité de sac à dos de 7 . Nous avons 4 articles. Leurs poids et valeurs sont:

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

Une méthode de force brute consisterait à prendre toutes les combinaisons possibles d'éléments. Ensuite, nous pouvons calculer leur poids total et les exclure qui dépassent la capacité de notre sac à dos et découvrir celui qui nous donne une valeur maximale. Pour 4 items, nous devrons vérifier ( 4! - 1 ) = 23 combinaisons possibles (sauf une avec aucun élément). Cela est assez lourd lorsque le nombre d'articles augmente. Voici quelques aspects que nous pouvons remarquer, à savoir:

• Nous pouvons prendre des éléments moins importants et calculer la valeur maximale que nous pouvons obtenir en utilisant ces articles et les combiner. Ainsi, notre problème peut être divisé en sous-problèmes.
• Si nous calculons les combinaisons pour l'article {1,2} , nous pouvons l'utiliser lorsque nous calculons {1, 2, 3} .
• Si nous minimisons le poids et maximisons la valeur, nous pouvons trouver notre solution optimale.

Pour ces raisons, nous utiliserons une programmation dynamique pour résoudre notre problème. Notre stratégie sera la suivante: chaque fois qu’un nouvel article arrive, nous vérifierons si nous pouvons choisir l’article ou non, et nous choisirons à nouveau les articles qui nous donneront une valeur maximale. Maintenant, si nous choisissons l'article, notre valeur sera la valeur de l'article, plus la valeur que nous pouvons obtenir en soustrayant la valeur de notre capacité et le maximum que nous pouvons obtenir pour ce poids restant. Si nous ne choisissons pas l'article, nous choisirons les articles qui nous donnent une valeur maximale sans inclure l'article. Essayons de le comprendre avec notre exemple:

Nous allons prendre une table de tableau 2D, où le nombre de colonnes sera la valeur maximale que nous pouvons obtenir en prenant les éléments + 1. Et le nombre de lignes sera le même que le nombre d'éléments. Notre tableau ressemblera à:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Nous avons intégré le poids et la valeur de chaque article au tableau pour notre commodité. N'oubliez pas que ceux-ci ne font pas partie du tableau, ils ne sont utilisés qu'à des fins de calcul, vous n'avez pas besoin de stocker ces valeurs dans un tableau .

Notre première colonne est remplie avec 0 . Cela signifie que si notre capacité maximale est 0 , quel que soit l'article que nous ayons, puisque nous ne pouvons pas choisir d'articles, notre valeur maximale sera 0 . Commençons par la table [0] [1] . Lorsque nous remplissons la table [1] [1] , nous nous demandons si notre capacité maximale était de 1 et que nous n'avions que le premier article, quelle serait notre valeur maximale? Le mieux que nous pouvons faire est 1 , en choisissant l'article. Pour la table [0] [2], cela signifie que si notre capacité maximale est 2 et que nous n'avons que le premier élément, la valeur maximale que nous pouvons obtenir est 1 . Ce sera la même chose pour la table [0] [3] , la table [0] [4] , la table [0] [5] , la table [0] [6] et la table [0] [7] . En effet, nous n’avons qu’un seul article, ce qui nous donne une valeur de 1 . Puisque nous avons seulement 1 quantité de chaque article, peu importe la façon dont nous augmentons la capacité de notre sac à dos, d'un élément, 1 est la meilleure valeur que nous pouvons faire. Donc, notre tableau ressemblera à:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Passons maintenant, pour la table [1] [1] , nous nous demandons si nous avions les articles 1 et 2 et si la capacité maximale de notre sac à dos était de 1 , quelle est la valeur maximale que nous pouvons obtenir? Si nous prenons les deux points 1 et 2 , le poids total sera 4 , ce qui dépassera notre capacité actuelle de sac à dos. Le point 2 ne peut donc pas être sélectionné. Maintenant, que pouvons-nous faire de mieux sans prendre le point 2 ? La valeur du haut, c'est-à-dire la table [0] [1] qui contient la valeur maximale que nous pouvons obtenir si nous avions la capacité maximale 1 et que nous n'avons pas choisi le second élément. Pour le tableau [1] [2] , 2 étant inférieur au poids [2] , c'est-à-dire le poids du deuxième élément, nous ne pouvons pas prendre l'article. Nous pouvons donc établir que, si le poids de l'article actuel est supérieur à notre capacité maximale, nous ne pouvons pas prendre cet article. Dans ce cas, nous allons simplement prendre la valeur du haut, qui représente la valeur maximale que nous pouvons prendre en excluant l'élément.

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

Maintenant, pour la table [1] [3], notre capacité maximale étant égale à notre poids actuel, nous avons deux choix.

• Nous sélectionnons l'article et ajoutons sa valeur à la valeur maximale que nous pouvons obtenir des autres articles restants après avoir pris cet article.
• Nous pouvons exclure cet article.

Parmi les deux choix, nous choisirons celui dont nous pouvons obtenir la valeur maximale. Si nous sélectionnons l'élément, nous obtenons: valeur pour cet élément + valeur maximale des autres éléments après avoir pris cet élément = 4 + 0 = 4 . Nous obtenons 4 (valeur de l'élément) de notre tableau de poids et le 0 (valeur maximale que nous pouvons obtenir du reste des articles après avoir pris cet article) vient en allant de 1 au dessus et de 3 pas en arrière. C'est la table [0] [0] . Pourquoi? Si nous prenons l'article, notre capacité restante sera 3 - 3 = 0 et l'article restant sera le premier article. Eh bien, si vous vous souvenez, la table [0] [0] stocke la valeur maximale que nous pouvons obtenir si notre capacité était égale à 0 et nous n’avons eu que le premier élément. Maintenant, si nous ne sélectionnons pas l'élément, la valeur maximale que nous pouvons obtenir provient d' une étape ci-dessus, à savoir 1 . Maintenant, nous prenons le maximum de ces deux valeurs ( 4 , 1 ) et définissons le tableau [1] [2] = 4 . Pour le tableau [1] [4] , étant donné que 4 , la capacité maximale du sac à dos est supérieure à 3 , le poids de notre article actuel, nous avons à nouveau deux options. On prend max ( Weight [2] + Table [0] [4-Weight [2]] , Table [0] [4] ) = max ( Weight [2] + Table [0] [1] , Table [0] [4] ) = max ( 4 + 1 , 1 ) = 5 .

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

En utilisant ces deux formules, nous pouvons remplir tout le tableau Table . Notre tableau ressemblera à:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

Ici, la dernière valeur que nous avons insérée dans notre tableau, le tableau [3] [7] contient notre valeur maximale requise. C'est la valeur maximale que nous pouvons obtenir si nous avions 4 articles et notre capacité maximale du sac à dos était de 7 .

Il ne faut pas oublier que, même pour la première rangée, le poids peut être supérieur à la capacité du sac à dos. Nous devrons garder une autre contrainte pour vérifier la valeur tout en remplissant la première ligne. Ou nous pouvons simplement prendre une autre ligne et définir toutes les valeurs de la première ligne à 0 . Le pseudo-code ressemblerait à ceci:

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

La complexité temporelle de cet algorithme est O(n*maxCapacity) , où n est le nombre d'éléments et maxCapacity est la capacité maximale de notre sac à dos.

Jusqu'à présent, nous avons trouvé la valeur maximale que nous pouvons tirer de notre exemple. Une question demeure. Quels sont les articles réels? Nous retracerons les valeurs dans notre tableau Table pour découvrir les éléments que nous avons pris. Nous suivrons deux stratégies:

• Pour tout élément, si la valeur provient de la position ci-dessus, nous n'avons pas pris l'article en cours. Nous allons 1 étape ci-dessus.
• Si la valeur ne vient pas de la position ci-dessus, nous avons pris l'article. Donc, nous allons 1 pas au-dessus et x recule où x est le poids de l'article en cours.

Le pseudo-code sera:

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

Si nous retraçons notre exemple, nous aurons:

De cela, nous pouvons dire cela, nous pouvons prendre les points 2 et 3 pour obtenir la valeur maximale.