le problème du sac à dos
j’ai trouvé le problème du sac à dos délicat et intéressant en même temps. Je suis sûr que si vous visitez cette page, vous connaissez déjà l’énoncé du problème mais juste pour l’achèvement :
problème:
étant donné un sac À Dos d’une capacité maximale de W et N Articles chacun avec sa propre valeur et poids, jetez les articles à l’intérieur du sac à dos de sorte que le contenu final Oups !!,
Voici la façon générale d’expliquer le problème – 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 la prend ou laisse
Exemple :
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
Un coup d’oeil sur les données d’exemple, nous dit que la valeur max que nous accommoder avec la limite de poids maximum de 10 à 50 + 40 = 90 avec un poids de 7.
approche:
la façon dont cela est résolu de manière optimale est d’utiliser la programmation dynamique – résolution pour les petits ensembles de problèmes de sac à dos, puis de les étendre pour le plus gros problème.,
construisons un tableau de poids Item x appelé V (tableau de valeurs):
V = 4 rows * 10 columnschacune des valeurs de cette matrice représente un problème de Sac À Dos plus petit.
cas de Base 1 : prenons le cas de la 0ème colonne. Cela signifie simplement que le sac à dos a 0 capacité. Que pouvez-vous tenir en eux? Rien. Alors, remplissons-les tous avec des 0.
cas de Base 2 : prenons le cas de la ligne 0. Cela signifie simplement qu’il n’y a pas d’éléments dans la maison. Que tenez-vous dans votre sac à dos s’il n’y a pas d’articles. Rien de nouveau !!! Tous les zéros.,
la Solution:
1) Maintenant, nous allons commencer à remplir le tableau de la ligne sage. Que signifient la ligne 1 et la colonne 1? Cela étant donné le premier élément (Ligne), pouvez-vous l’accueillir dans le sac à dos de capacité 1 (colonne). Nope. Le poids du premier article est de 5. Alors, remplissons 0. En fait, nous ne serions pas en mesure de remplir quoi que ce soit jusqu’à ce que nous atteignions la colonne 5 (Poids 5).
2) Une fois que nous atteignons la colonne 5 (qui représente le poids 5) sur la première rangée, cela signifie que nous pourrions accueillir l’élément 1., Remplissons 10 là-bas (rappelez – vous, c’est un tableau de valeurs):
3) en continuant, pour le poids 6 (colonne 6), pouvons – nous accueillir autre chose avec le poids restant de 1 (Poids-poids de cet article => 6-5). Hey, rappelez-vous, nous sommes sur le premier élément. Donc, il est assez intuitif que le reste de la ligne sera juste la même valeur aussi puisque nous ne pouvons pas ajouter un autre élément pour ce poids supplémentaire que nous avons.,
4) Donc, la prochaine chose intéressante qui se passe lorsque nous arrivons à la colonne 4 de la troisième rangée. Le poids courant est de 4.
nous devrions vérifier les cas suivants.
1) pouvons – nous accueillir L’article 2-Oui, nous pouvons. Le poids de l’article 2 est de 4.
2) La valeur du poids actuel est-elle plus élevée sans L’élément 2? – Vérifier la rangée précédente pour le même poids. Nope. la rangée précédente * contient 0, car nous n’avons pas pu accueillir l’article 1 en poids 4.
3) pouvons-nous accueillir deux articles dans le même poids afin que nous puissions maximiser la valeur? – Nope., Le poids restant après déduction du poids de L’article2 est 0.
Pourquoi la ligne précédente?
simplement parce que la ligne précédente au poids 4 elle-même est une solution de sac à dos plus petite qui donne la valeur maximale qui pourrait être accumulée pour ce poids jusqu’à ce point (en traversant les éléments).,
en Exemplifiant,
1) La valeur de l’élément courant = 40
2) Le poids de l’élément courant = 4
3) Le poids qui est laissé plus = 4 – 4 = 0
4) Vérification de la ligne ci-dessus (l’Article ci-dessus dans le cas de l’Article 1 ou le cumul de la valeur Max dans le cas du reste des lignes). Pour le poids restant 0, sommes-nous en mesure d’accueillir L’article 1? Tout simplement, est-il une quelconque valeur dans la ligne ci-dessus pour le poids?,
Le calcul est comme suit :
1) Prendre la valeur maximale pour le même poids, sans cet élément:
previous row, same weight = 0=> V2) Prendre la valeur de l’élément courant + valeur que nous accommoder avec le poids restant:
Max entre les deux est de 40 (0 et 40).
3) l’événement suivant et le plus important se produit à la colonne 9 et à la ligne 2. Ce qui signifie que nous avons un poids de 9 et nous avons deux éléments. En regardant les données d’exemple, nous pourrions accueillir les deux premiers éléments., Ici, nous considérons que peu de choses:
- La valeur de l’élément courant = 40
- Le poids de l’élément courant = 4
- Le poids qui est laissé plus = 9 – 4 = 5
- Vérifiez la ligne ci-dessus. Le poids restant 5, sommes-nous en mesure d’accueillir l’Article 1.
Donc, le calcul est le suivant :
1) Prendre la valeur maximale pour le même poids, sans cet élément:
previous row, same weight = 102) Prendre la valeur de l’élément courant + valeur que nous pourrions accumuler avec le reste de poids:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,
à la fin de la résolution de tous ces petits problèmes, il suffit de renvoyer la valeur à V – Item 4 au poids 10:
complexité
analyser la complexité de la solution est assez simple. Nous avons juste une boucle pour W dans une boucle de N = > O (NW)
implémentation:
Voici le code d’implémentation obligatoire en Java: