mise à Jour: Lire sur l’optimisation de l’espace de la complexité de la programmation dynamique de la solution dans mon article ici.,
le problème du Sac À Dos est un problème vraiment intéressant en combinatoire — pour citer Wikipedia,
« étant donné un ensemble d’éléments, chacun avec un poids et une valeur, déterminez le nombre de chaque élément à inclure dans une collection afin que le poids total soit inférieur ou égal à une limite donnée et que la valeur totale soit aussi grande que possible. »
de Wikipedia, nous voyons qu’il existe quelques variantes du problème du Sac À Dos: 0-1 sac à dos, Sac À Dos borné et sac à dos non borné., Aujourd’hui, nous allons nous concentrer sur la variante la plus courante (et la plus simple): le problème du sac à dos 0-1.
un phrasé légèrement plus intéressant et relatable du problème du sac à dos 0-1 est:
considérez qu’un voleur entre dans une maison pour voler et qu’il porte un sac à dos. Il y a un nombre fixe d’articles dans la maison — chacun avec son propre poids et valeur — bijoux, avec moins de poids et la valeur la plus élevée vs tables, avec moins de valeur mais beaucoup lourd. Pour ajouter du carburant au feu, le voleur a un vieux sac à dos qui a une capacité limitée., Évidemment, il ne peut pas diviser la table en deux ou les bijoux en 3/4ème. Il le prend ou le laisse. Source
Malheureusement, j’ai eu quelques difficultés à comprendre certaines parties de la Hackerearth l’article, c’est pourquoi j’ai décidé d’écrire mon propre article. Cet article sera largement basé sur L’article de Hackerearth et les extraits de code sont écrits en Java. Je vais me pencher sur des explications et des élaborations supplémentaires lorsque je pense qu’elles sont nécessaires.
Nous allons résoudre ce problème avec la programmation dynamique., La programmation dynamique nécessite une sous-structure optimale et des sous-problèmes qui se chevauchent, qui sont tous deux présents dans le problème du sac à dos 0-1, comme nous le verrons.
c’est bien si vous ne comprenez pas ce que sont « sous-structure optimale” et « sous-problèmes qui se chevauchent” (c’est un article pour un autre jour). Essentiellement, cela signifie simplement une saveur particulière de problèmes qui nous permettent de réutiliser les solutions précédentes à des problèmes plus petits afin de calculer une solution au problème actuel. Vous verrez ce que je veux dire dans un peu.,
détails du problème
comme il s’agit du problème du sac à dos 0-1, nous pouvons soit inclure un élément dans notre sac à dos, soit l’exclure, mais ne pas en inclure une fraction, soit l’inclure plusieurs fois.
Solution
tout d’abord, nous créons un tableau à 2 dimensions (c’est-à-dire une table) de n + 1 lignes et w + 1 colonnes.
un numéro de ligne I représente l’ensemble de tous les éléments des lignes 1 à I. Par exemple, les valeurs de la ligne 3 supposent que nous n’avons que les éléments 1, 2 et 3.
Un numéro de colonne j représente la capacité de poids de notre sac à dos., Par conséquent, les valeurs de la colonne 5, par exemple, supposent que notre sac à dos peut contenir 5 unités de poids.
en mettant tout ensemble, une entrée dans la ligne i, la colonne j représente la valeur maximale qui peut être obtenue avec les éléments 1, 2, 3 i i, dans un sac à dos pouvant contenir j unités de poids.
nous allons appeler notre table mat de la matrice. Par conséquent, int mat = new int.
Étape 2:
Nous pouvons immédiatement commencer à remplir certaines entrées dans notre tableau: les cas de base, pour lesquels la solution est triviale., Par exemple, à la ligne 0, lorsque nous n’avons aucun élément à choisir, la valeur maximale pouvant être stockée dans n’importe quel sac à dos doit être 0. De même, à la colonne 0, pour un sac à dos pouvant contenir 0 Unité de poids, la valeur maximale qui peut y être stockée est 0. (Nous supposons qu’il n’y a pas d’objets de valeur sans masse.)
On peut le faire avec 2 boucles for:
l’Étape 3 (le noeud du problème):
Maintenant, nous voulons commencer à peupler notre table., Comme pour toutes les solutions de programmation dynamique, à chaque étape, nous utiliserons nos solutions aux sous-problèmes précédents.
je vais d’abord décrire la logique, avant de montrer un exemple concret.
la relation entre la valeur de la ligne i, de la colonne j et les valeurs des sous-problèmes précédents est la suivante:
rappelons qu’à la ligne i et à la colonne j, Nous abordons un sous-problème composé des éléments 1, 2, 3 i i avec un sac à dos de capacité J. Il y a 2 options à ce stade: nous pouvons inclure l’élément i ou non., Par conséquent, nous devons comparer la valeur maximale que nous pouvons obtenir avec et sans l’élément I.
la valeur maximale que nous pouvons obtenir sans l’élément i se trouve à la ligne i-1, colonne J. cette partie est facile. Le raisonnement est simple: quelle que soit la valeur maximale que nous pouvons obtenir avec les articles 1, 2, 3 i je dois évidemment être la même valeur maximale que nous pouvons obtenir avec les articles 1, 2, 3 i i – 1, si nous choisissons de ne pas inclure l’article I.
pour calculer la valeur maximale que nous pouvons obtenir avec l’article i, nous devons d’abord comparer le poids de l’article I avec la capacité de poids du sac à dos., Évidemment, si l’article I pèse plus que ce que le sac à dos peut contenir, nous ne pouvons pas l’inclure, il n’a donc pas de sens d’effectuer le calcul. Dans ce cas, la solution à ce problème est simplement la valeur maximale que nous pouvons obtenir sans l’élément i (c’est-à-dire la valeur dans la ligne ci-dessus, dans la même colonne).
cependant, supposons que l’article I pèse moins que la capacité du sac à dos. Nous avons donc la possibilité de l’inclure, si elle augmente potentiellement la valeur maximale., La valeur maximale pouvant être obtenue en incluant l’élément i est donc = la valeur de l’élément i lui-même + la valeur maximale pouvant être obtenue avec la capacité restante du sac à dos. Nous voulons évidemment utiliser pleinement la capacité de notre sac à dos et ne laisser aucune capacité restante être gaspillée.
Par conséquent, à la ligne i et à la colonne j (qui représente la valeur maximale que nous pouvons y obtenir), nous choisirions soit la valeur maximale que nous pouvons obtenir sans l’élément i, soit la valeur maximale que nous pouvons obtenir avec l’élément i, selon la valeur la plus grande.
Voici un exemple concret de ce que je veux dire.,
À la ligne 3 (item 2), et la colonne 5 (sac à dos capacité de 4), nous pouvons choisir d’inscrire le point 2 (qui pèse 4 unités) ou pas. Si nous choisissons de ne pas l’inclure, la valeur maximale que nous pouvons obtenir est la même que si nous n’avons que l’élément 1 à choisir (qui se trouve dans la ligne ci-dessus, c’est-à-dire 0)., Si nous voulons inclure l’élément 2, la valeur maximale que nous pouvons obtenir avec l’élément 2 est la valeur de l’élément 2 (40) + la valeur maximale que nous pouvons obtenir avec la capacité restante (qui est 0, car le sac à dos est déjà complètement plein).
à la ligne 3 (article 2) et à la colonne 10 (Capacité du sac à dos de 9), encore une fois, nous pouvons choisir d’inclure l’article 2 ou non. Si nous choisissons de ne pas le faire, la valeur maximale que nous pouvons obtenir est la même que celle de la ligne ci-dessus dans la même colonne, c’est-à-dire 10 (en incluant uniquement l’élément 1, qui a une valeur de 10). Si nous incluons l’article 2, nous avons une capacité de sac à dos restante de 9-4 = 5., Nous pouvons trouver la valeur maximale qui peut être obtenue avec une capacité de 5 en regardant la ligne ci-dessus, à la colonne 5. Ainsi, la valeur maximale que nous pouvons obtenir en incluant l’élément 2 est 40 (la valeur de l’élément 2) + 10 = 50.
Nous choisissons le plus grand entre 50 et 10, et donc la valeur maximale que nous pouvons obtenir avec les articles 1 et 2, avec une capacité de sac à dos de 9, est de 50.,
L’algorithme peut être exprimé en Java comme ceci:
Étape 4 (solution finale):
Une fois la table remplie, la solution finale peut être trouvée à la dernière ligne de la dernière colonne, qui représente la valeur maximale obtenue avec tous les articles et la pleine capacité du sac à dos.
return mat;
code de travail:
remarque: ici, j’ai imprimé la réponse finale au lieu de la renvoyer, car tout est logé sous public static void main.,
Thanks for reading!