Ici, le sac à dos est comme un récipient ou un sac. Supposons que nous ayons donné des éléments qui ont un certain poids ou un certain bénéfice. Nous devons mettre certains objets dans le sac à dos de manière à ce que la valeur totale produise un profit maximum.

Par exemple, le poids du conteneur est de 20 kg. Nous devons sélectionner les articles de telle manière que la somme des poids des articles soit inférieure ou égale au poids du conteneur et que le profit soit maximum.

Il existe deux types de problèmes de sac à dos :

• Problème de sac à dos 0/1
• Problème de sac à dos fractionnaire

Nous discuterons des deux problèmes un par un. Tout d’abord, nous découvrirons le problème du sac à dos 0/1.

Quel est le problème du sac à dos 0/1 ?

Le problème du sac à dos 0/1 signifie que les éléments sont complètement ou aucun élément n'est rempli dans un sac à dos. Par exemple, nous avons deux articles pesant respectivement 2 kg et 3 kg. Si nous sélectionnons l'article de 2 kg, nous ne pouvons pas sélectionner l'article de 1 kg parmi l'article de 2 kg (l'article n'est pas divisible) ; nous devons choisir complètement l'article de 2 kg. Il s'agit d'un problème de sac à dos 0/1 dans lequel soit nous sélectionnons l'élément complètement, soit nous choisissons cet élément. Le problème du sac à dos 0/1 est résolu par la programmation dynamique.

Quel est le problème du sac à dos fractionnaire ?

Le problème du sac à dos fractionnaire signifie que nous pouvons diviser l’article. Par exemple, nous avons un article de 3 kg alors nous pouvons prélever l’article de 2 kg et laisser l’article de 1 kg. Le problème du sac à dos fractionnaire est résolu par l’approche Greedy.

Exemple de problème de sac à dos 0/1.

Considérez le problème avec les poids et les bénéfices :

Poids : {3, 4, 6, 5}

Bénéfices : {2, 3, 1, 4}

Le poids du sac à dos est de 8 kg

Le nombre d'articles est de 4

Le problème ci-dessus peut être résolu en utilisant la méthode suivante :

X_je= {1, 0, 0, 1}

= {0, 0, 0, 1}

faire en java

= {0, 1, 0, 1}

Ci-dessus sont les combinaisons possibles. 1 indique que l'article est entièrement prélevé et 0 signifie qu'aucun article n'est prélevé. Puisqu’il y a 4 éléments, les combinaisons possibles seront :

2⁴= 16 ; Donc. Il existe 16 combinaisons possibles qui peuvent être réalisées en utilisant le problème ci-dessus. Une fois toutes les combinaisons réalisées, nous devons sélectionner celle qui procure le maximum de profit.

Une autre approche pour résoudre le problème est l’approche de programmation dynamique. Dans l'approche de programmation dynamique, le problème compliqué est divisé en sous-problèmes, puis on trouve la solution d'un sous-problème et la solution du sous-problème sera utilisée pour trouver la solution d'un problème complexe.

Comment ce problème peut-il être résolu en utilisant l’approche de programmation dynamique ?

D'abord,

nous créons une matrice présentée comme ci-dessous :

Dans la matrice ci-dessus, les colonnes représentent le poids, c'est-à-dire 8. Les lignes représentent les bénéfices et le poids des éléments. Ici, nous n'avons pas pris directement le poids 8, le problème est divisé en sous-problèmes, c'est-à-dire 0, 1, 2, 3, 4, 5, 6, 7, 8. La solution des sous-problèmes serait enregistrée dans le les cellules et la réponse au problème seraient stockées dans la cellule finale. Tout d’abord, nous écrivons les poids dans l’ordre croissant et les bénéfices en fonction de leurs poids indiqués ci-dessous :

Dans_je= {3, 4, 5, 6}

p_je= {2, 3, 4, 1}

La première ligne et la première colonne seraient 0 car il n'y a aucun élément pour w=0

Quand i=1, W=1

Dans₁= 3 ; Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids de 3, mais que la capacité du sac à dos est de 1. Nous ne pouvons pas remplir l'élément de 3 kg dans le sac à dos d'une capacité de 1 kg, alors ajoutez 0 à M[1][1] indiqué comme ci-dessous. :

Quand je = 1, W = 2

Dans₁= 3 ; Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids de 3, mais que la capacité du sac à dos est de 2. Nous ne pouvons pas remplir l'élément de 3 kg dans le sac à dos d'une capacité de 2 kg, alors ajoutez 0 à M[1][2] indiqué comme ci-dessous. :

Quand i=1, W=3

Dans₁= 3 ; Puisque nous n’avons qu’un seul élément dans l’ensemble ayant un poids égal à 3 et que le poids du sac à dos est également 3 ; par conséquent, nous pouvons remplir le sac à dos avec un élément de poids égal à 3. Nous mettons le profit correspondant au poids 3, soit 2 à M[1][3] comme ci-dessous :

Quand i=1, W = 4

_W1= 3 ; Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids égal à 3 et que le poids du sac à dos est de 4 ; par conséquent, nous pouvons remplir le sac à dos avec un élément de poids égal à 3. Nous mettons le profit correspondant au poids 3, soit 2 à M[1][4] comme ci-dessous :

Quand i=1, W = 5

_W1= 3 ; Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids égal à 3 et que le poids du sac à dos est de 5 ; par conséquent, nous pouvons remplir le sac à dos avec un élément de poids égal à 3. Nous mettons le profit correspondant au poids 3, soit 2 à M[1][5] comme ci-dessous :

Quand je =1, W=6

_W1= 3 ; Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids égal à 3 et que le poids du sac à dos est de 6 ; par conséquent, nous pouvons remplir le sac à dos avec un élément de poids égal à 3. Nous mettons le profit correspondant au poids 3, soit 2 à M[1][6] comme ci-dessous :

Quand i=1, W = 7

_W1= 3 ; Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids égal à 3 et que le poids du sac à dos est de 7 ; par conséquent, nous pouvons remplir le sac à dos avec un élément de poids égal à 3. Nous mettons le profit correspondant au poids 3, soit 2 à M[1][7] comme ci-dessous :

Quand je =1, W =8

_W1= 3 ; Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids égal à 3 et que le poids du sac à dos est de 8 ; par conséquent, nous pouvons remplir le sac à dos avec un élément de poids égal à 3. Nous mettons le profit correspondant au poids 3, soit 2 à M[1][8] comme ci-dessous :

Maintenant, la valeur de « i » est incrémentée et devient 2.

Quand je =2, W = 1

Le poids correspondant à la valeur 2 est 4, soit w₂= 4. Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids égal à 4 et que le poids du sac à dos est 1. Nous ne pouvons pas mettre l'élément de poids 4 dans un sac à dos, nous ajoutons donc 0 à M[2][1 ] illustré comme ci-dessous :

Quand je =2, W = 2

Le poids correspondant à la valeur 2 est 4, soit w₂= 4. Puisque nous n'avons qu'un seul élément dans l'ensemble ayant un poids égal à 4 et que le poids du sac à dos est 2. Nous ne pouvons pas mettre l'élément de poids 4 dans un sac à dos, nous ajoutons donc 0 à M[2][2 ] illustré comme ci-dessous :

Quand je =2, W = 3

Le poids correspondant à la valeur 2 est 4, soit w₂= 4. Puisque nous avons deux éléments dans l'ensemble ayant des poids 3 et 4, et que le poids du sac à dos est 3. Nous pouvons mettre l'élément de poids 3 dans un sac à dos, nous ajoutons donc 2 en M[2][3] montré comme ci-dessous:

Quand je =2, W = 4

Le poids correspondant à la valeur 2 est 4, soit w₂= 4. Puisque nous avons deux éléments dans l'ensemble ayant des poids 3 et 4, et que le poids du sac à dos est de 4. Nous pouvons mettre l'élément de poids 4 dans un sac à dos car le profit correspondant au poids 4 est supérieur à celui de l'élément ayant un poids. 3, nous ajoutons donc 3 à M[2][4] comme ci-dessous :

Quand je = 2, W = 5

Le poids correspondant à la valeur 2 est 4, soit w₂= 4. Puisque nous avons deux éléments dans l'ensemble ayant des poids 3 et 4, et que le poids du sac à dos est de 5. Nous pouvons mettre un élément de poids 4 dans un sac à dos et le profit correspondant au poids est de 3, nous ajoutons donc 3 à M[2][5] illustré ci-dessous :

Quand je = 2, W = 6

Le poids correspondant à la valeur 2 est 4, soit w₂= 4. Puisque nous avons deux éléments dans l'ensemble ayant des poids 3 et 4, et que le poids du sac à dos est de 6. Nous pouvons mettre un élément de poids 4 dans un sac à dos et le profit correspondant au poids est de 3, nous ajoutons donc 3 à M[2][6] illustré ci-dessous :

Quand je = 2, W = 7

Le poids correspondant à la valeur 2 est 4, soit w₂= 4. Puisque nous avons deux éléments dans l'ensemble ayant des poids 3 et 4, et que le poids du sac à dos est 7. Nous pouvons mettre un élément de poids 4 et 3 dans un sac à dos et les bénéfices correspondant aux poids sont 2 et 3 ; par conséquent, le profit total est de 5, nous ajoutons donc 5 à M[2][7] comme ci-dessous :

Quand je = 2, W = 8

Le poids correspondant à la valeur 2 est 4, soit w₂= 4. Puisque nous avons deux éléments dans l'ensemble ayant des poids 3 et 4, et que le poids du sac à dos est 7. Nous pouvons mettre un élément de poids 4 et 3 dans un sac à dos et les bénéfices correspondant aux poids sont 2 et 3 ; par conséquent, le profit total est de 5, nous ajoutons donc 5 à M[2][7] comme ci-dessous :

Maintenant, la valeur de « i » est incrémentée et devient 3.

Quand je = 3, W = 1

contient la sous-chaîne java

Le poids correspondant à la valeur 3 est 5, soit w₃= 5. Puisque nous avons trois éléments dans l'ensemble ayant des poids 3, 4 et 5, et que le poids du sac à dos est 1. Nous ne pouvons mettre aucun des éléments dans un sac à dos, nous ajoutons donc 0 à M[3][ 1] illustré ci-dessous :

Quand je = 3, W = 2

Le poids correspondant à la valeur 3 est 5, soit w₃= 5. Puisque nous avons trois éléments dans l'ensemble ayant un poids de 3, 4 et 5, et que le poids du sac à dos est de 1. Nous ne pouvons mettre aucun des éléments dans un sac à dos, nous ajoutons donc 0 à M[3][ 2] comme ci-dessous :

Quand je = 3, W = 3

Le poids correspondant à la valeur 3 est 5, soit w₃= 5. Puisque nous avons trois éléments dans l'ensemble de poids 3, 4 et 5 respectivement et que le poids du sac à dos est de 3. L'élément avec un poids 3 peut être mis dans le sac à dos et le profit correspondant à l'élément est de 2, nous ajoutons donc 2 à M[3][3] comme ci-dessous :

Quand je = 3, W = 4

Le poids correspondant à la valeur 3 est 5, soit w₃= 5. Puisque nous avons trois éléments dans l'ensemble de poids 3, 4 et 5 respectivement, et que le poids du sac à dos est de 4. Nous pouvons conserver l'élément de poids 3 ou 4 ; le profit (3) correspondant au poids 4 est supérieur au profit correspondant au poids 3 donc on ajoute 3 à M[3][4] comme ci-dessous :

Quand je = 3, W = 5

Le poids correspondant à la valeur 3 est 5, soit w₃= 5. Puisque nous avons trois éléments dans l'ensemble de poids 3, 4 et 5 respectivement, et que le poids du sac à dos est de 5. Nous pouvons conserver l'élément de poids 3, 4 ou 5 ; le profit (3) correspondant au poids 4 est supérieur aux profits correspondant aux poids 3 et 5 donc on ajoute 3 à M[3][5] comme ci-dessous :

Quand je =3, W = 6

Le poids correspondant à la valeur 3 est 5, soit w₃= 5. Puisque nous avons trois éléments dans l'ensemble de poids 3, 4 et 5 respectivement, et que le poids du sac à dos est de 6. Nous pouvons conserver l'élément de poids 3, 4 ou 5 ; le profit (3) correspondant au poids 4 est supérieur aux profits correspondant aux poids 3 et 5 donc on ajoute 3 à M[3][6] comme ci-dessous :

Quand je =3, W = 7

Le poids correspondant à la valeur 3 est 5, soit w₃= 5. Puisque nous avons trois éléments dans l'ensemble de poids 3, 4 et 5 respectivement, et que le poids du sac à dos est de 7. Dans ce cas, nous pouvons conserver les deux éléments de poids 3 et 4, la somme du profit serait égal à (2 + 3), c'est-à-dire 5, nous ajoutons donc 5 à M[3][7] comme ci-dessous :

Quand je = 3, W = 8

Le poids correspondant à la valeur 3 est 5, soit w₃= 5. Puisque nous avons trois éléments dans l'ensemble de poids 3, 4 et 5 respectivement, et que le poids du sac à dos est 8. Dans ce cas, nous pouvons conserver les deux éléments de poids 3 et 4, la somme des le profit serait égal à (2 + 3), soit 5, nous ajoutons donc 5 à M[3][8] comme ci-dessous :

Maintenant, la valeur de « i » est incrémentée et devient 4.

Quand je = 4, W = 1

Le poids correspondant à la valeur 4 est 6, soit w₄= 6. Puisque nous avons quatre éléments dans l’ensemble des poids 3, 4, 5 et 6 respectivement, et que le poids du sac à dos est 1. Le poids de tous les éléments est supérieur au poids du sac à dos, nous ne pouvons donc pas ajoutez n'importe quel objet dans le sac à dos ; Par conséquent, nous ajoutons 0 à M[4][1] comme ci-dessous :

Quand je = 4, W = 2

Le poids correspondant à la valeur 4 est 6, soit w₄= 6. Puisque nous avons quatre éléments dans l’ensemble des poids 3, 4, 5 et 6 respectivement, et que le poids du sac à dos est 2. Le poids de tous les éléments est supérieur au poids du sac à dos, nous ne pouvons donc pas ajoutez n'importe quel objet dans le sac à dos ; Par conséquent, nous ajoutons 0 à M[4][2] comme ci-dessous :

Quand je = 4, W = 3

Le poids correspondant à la valeur 4 est 6, soit w₄= 6. Puisque nous avons quatre éléments dans l'ensemble des poids 3, 4, 5 et 6 respectivement, et que le poids du sac à dos est 3. L'élément avec un poids 3 peut être mis dans le sac à dos et le profit correspondant au le poids 4 est 2, nous ajouterons donc 2 à M[4][3] comme ci-dessous :

Quand je = 4, W = 4

Le poids correspondant à la valeur 4 est 6, soit w₄= 6. Puisque nous avons quatre éléments dans l'ensemble des poids 3, 4, 5 et 6 respectivement, et que le poids du sac à dos est 4. L'élément avec un poids 4 peut être mis dans le sac à dos et le bénéfice correspondant au le poids 4 est 3, nous ajouterons donc 3 à M[4][4] comme ci-dessous :

Quand je = 4, W = 5

Le poids correspondant à la valeur 4 est 6, soit w₄= 6. Puisque nous avons quatre éléments dans l'ensemble des poids 3, 4, 5 et 6 respectivement, et que le poids du sac à dos est 5. L'élément avec un poids 4 peut être mis dans le sac à dos et le bénéfice correspondant au le poids 4 est 3, nous ajouterons donc 3 à M[4][5] comme ci-dessous :

Quand je = 4, W = 6

Le poids correspondant à la valeur 4 est 6, soit w₄= 6. Puisque nous avons quatre éléments dans l'ensemble de poids 3, 4, 5 et 6 respectivement, et que le poids du sac à dos est de 6. Dans ce cas, nous pouvons mettre les éléments dans le sac à dos de poids 3, 4. , 5 ou 6 mais le profit, c'est-à-dire 4 correspondant au poids 6, est le plus élevé de tous les éléments ; par conséquent, nous ajoutons 4 à M[4][6] comme ci-dessous :

Quand je = 4, W = 7

Le poids correspondant à la valeur 4 est 6, soit w₄= 6. Puisque nous avons quatre éléments dans l'ensemble des poids 3, 4, 5 et 6 respectivement, et que le poids du sac à dos est de 7. Ici, si nous ajoutons deux éléments de poids 3 et 4, cela produira le maximum profit, c'est-à-dire que (2 + 3) est égal à 5, nous ajoutons donc 5 à M[4][7] comme ci-dessous :

vider le cache npm

Quand je = 4, W = 8

Le poids correspondant à la valeur 4 est 6, soit w₄= 6. Puisque nous avons quatre éléments dans l'ensemble des poids 3, 4, 5 et 6 respectivement, et que le poids du sac à dos est de 8. Ici, si nous ajoutons deux éléments de poids 3 et 4, cela produira le maximum profit, c'est-à-dire que (2 + 3) est égal à 5, nous ajoutons donc 5 à M[4][8] comme ci-dessous :

Comme nous pouvons le constater dans le tableau ci-dessus, 5 est le profit maximum parmi toutes les entrées. Le pointeur pointe vers la dernière ligne et la dernière colonne ayant 5 valeurs. Nous allons maintenant comparer la valeur 5 avec la ligne précédente ; si la ligne précédente, c'est-à-dire i = 3, contient la même valeur 5, alors le pointeur se déplacera vers le haut. Puisque la ligne précédente contient la valeur 5, le pointeur sera déplacé vers le haut comme indiqué dans le tableau ci-dessous :

Encore une fois, nous comparerons la valeur 5 de la ligne ci-dessus, c'est-à-dire i = 2. Puisque la ligne ci-dessus contient la valeur 5, le pointeur sera à nouveau déplacé vers le haut, comme indiqué dans le tableau ci-dessous :

Encore une fois, nous comparerons la valeur 5 de la ligne ci-dessus, c'est-à-dire i = 1. Puisque la ligne ci-dessus ne contient pas la même valeur, nous considérerons la ligne i = 1 et le poids correspondant à la ligne est 4. Par conséquent , nous avons sélectionné le poids 4 et nous avons rejeté les poids 5 et 6 indiqués ci-dessous :

X = { 1, 0, 0}

Le profit correspondant au poids est 3. Par conséquent, le profit restant est (5 - 3) égal à 2. Nous allons maintenant comparer cette valeur 2 avec la ligne i = 2. Puisque la ligne (i = 1) contient la valeur 2 ; par conséquent, le pointeur s'est déplacé vers le haut, comme indiqué ci-dessous :

Encore une fois, nous comparons la valeur 2 avec une ligne ci-dessus, c'est-à-dire i = 1. Puisque la ligne i = 0 ne contient pas la valeur 2, donc la ligne i = 1 sera sélectionnée et le poids correspondant à i = 1 est 3 affiché. ci-dessous:

X = {1, 1, 0, 0}

Le profit correspondant au poids est de 2. Par conséquent, le profit restant est de 0. Nous comparons la valeur 0 avec la ligne ci-dessus. Puisque la ligne ci-dessus contient une valeur 0 mais que le profit correspondant à cette ligne est 0. Dans ce problème, deux poids sont sélectionnés, c'est-à-dire 3 et 4 pour maximiser le profit.