dans ce tutoriel, plus tôt, Nous avons discuté du problème de sac à dos fractionnaire en utilisant une approche gourmande. Nous avons montré que L’approche gourmande donne une solution optimale pour le sac À Dos fractionné. Cependant, ce chapitre couvrira le problème du sac à dos 0-1 et son analyse.
Dans Le Sac À Dos 0-1, les articles ne peuvent pas être cassés, ce qui signifie que le voleur doit prendre l’article dans son ensemble ou le laisser., C’est la raison derrière l’appeler comme 0-1 Sac À Dos.
Par conséquent, dans le cas de 0-1 Sac À Dos, la valeur de xi peut être 0 ou 1, où les autres contraintes restent les mêmes.
Le sac à dos 0-1 ne peut pas être résolu par une approche gourmande. L’approche gourmande n’assure pas une solution optimale. Dans de nombreux cas, une approche gourmande peut donner une solution optimale.
Les exemples suivants établiront notre déclaration.
exemple-1
considérons que la capacité du sac à dos est W = 25 et les éléments sont comme indiqué dans le tableau suivant.,
| Item | Un | B | C | D |
|---|---|---|---|---|
| Profit | 24 | 18 | 18 | 10 |
| Poids | 24 | 10 | 10 | 7 |
Sans prendre en compte le bénéfice par unité de poids (pi/wi), si l’on applique Gourmand approche pour résoudre ce problème, le premier élément sera sélectionné comme il va contribuer un maximum de bénéfices entre tous les éléments.,
Après avoir sélectionné l’élément A, plus aucun élément ne sera sélectionné. Par conséquent, pour cet ensemble donné d’éléments, le bénéfice total est de 24. Alors que, la solution optimale peut être obtenue en sélectionnant des éléments, B et C, où le bénéfice total est de 18 + 18 = 36.
Exemple 2
au Lieu de sélectionner les éléments en fonction de l’intérêt général, dans cet exemple, les éléments sont sélectionnés sur la base de rapport pi/wi. Considérons que la capacité du sac à dos est W = 60 et les articles sont comme indiqué dans le tableau suivant.,
| Item | A | B | C |
|---|---|---|---|
| Price | 100 | 280 | 120 |
| Weight | 10 | 40 | 20 |
| Ratio | 10 | 7 | 6 |
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380., Cependant, la solution optimale de cette instance peut être obtenue en sélectionnant des éléments, B et C, où le bénéfice total est de 280 + 120 = 400.
Par conséquent, on peut conclure que L’approche gourmande peut ne pas donner une solution optimale.
pour résoudre 0-1 Sac À Dos, une approche de programmation dynamique est requise.
énoncé du problème
Un voleur vole un magasin et peut transporter un poids maximal de W dans son sac à dos. Il y a n articles et le poids de ith article est wi et le bénéfice de la sélection de cet article est pi. Quels objets le voleur doit-il prendre?,
approche de programmation dynamique
soit l’élément le plus numéroté dans une solution optimale s pour W dollars. Alors S ‘ = S – {i} est une solution optimale pour les dollars W – wi et la valeur de la solution S est Vi plus La valeur du sous-problème.
Nous pouvons exprimer ce fait dans la formule suivante: définir c comme étant la solution pour les éléments 1,2, … , i et le poids maximum W.,
L’algorithme prend les entrées suivantes
-
Le poids maximum W
-
Le nombre d’éléments n
-
Les deux séquences v = <v1, v2, …, vn> et w = <w1, w2, …, wn>
L’ensemble des éléments à prendre peut être déduite à partir de la table, commençant à c et de traçage vers l’arrière où les valeurs optimales sont venus.
analyse
Cet algorithme prend θ(n, w) fois que la table c A (n + 1).(w + 1) entrées, où chaque entrée nécessite θ (1) Temps de calcul.,