I denne tutorial, vi tidligere har diskuteret Relativ Tornyster problem ved hjælp af Grådige tilgang. Vi har vist, at grådige tilgang giver en optimal løsning for fraktioneret rygsæk. Men dette kapitel vil dække 0-1 rygsæk problem og dens analyse.
i 0-1 rygsæk kan genstande ikke brydes, hvilket betyder, at tyven skal tage varen som helhed eller forlade den., Dette er grunden til at kalde det som 0-1 rygsæk.
i tilfælde af 0-1 rygsæk kan værdien af .i derfor være enten 0 eller 1, hvor andre begrænsninger forbliver de samme.0-1 rygsæk kan ikke løses ved grådig tilgang. Grådig tilgang sikrer ikke en optimal løsning. I mange tilfælde kan grådig tilgang give en optimal løsning.
følgende eksempler vil fastlægge vores Erklæring.
eksempel-1
lad os overveje, at kapaciteten på rygsækken er 25 = 25, og elementerne er som vist i følgende tabel.,
| Post | A | B | C | D |
|---|---|---|---|---|
| Overskud | 24 | 18 | 18 | 10 |
| Vægt | 24 | 10 | 10 | 7 |
Uden at tage profit per enhed vægt (pi/wi), hvis vi anvender Grådige tilgang til at løse problemet, første element, En, vil blive udvalgt, da det vil bidrage maksimal profit blandt alle elementer.,
når du har valgt punkt A, vil der ikke blive valgt mere element. Derfor er det samlede overskud for dette givne sæt af varer 24. Mens den optimale løsning kan opnås ved at vælge emner, B og C, hvor det samlede overskud er 18 + 18 = 36.
eksempel-2
i stedet for at vælge elementerne baseret på den samlede fordel, vælges elementerne i dette eksempel baseret på forholdet pi / .i. Lad os overveje, at rygsækkenes kapacitet er 60 = 60, og elementerne er som vist i nedenstående tabel.,
| 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., Den optimale løsning af dette tilfælde kan imidlertid opnås ved at vælge emner, B og C, hvor det samlede overskud er 280 + 120 = 400.
derfor kan det konkluderes, at grådige tilgang ikke kan give en optimal løsning.
for at løse 0-1 rygsæk kræves dynamisk programmeringsmetode.
problemformulering
en tyv røver en butik og kan bære en maksimal vægt af.ind i hans rygsæk. Der er n elementer og vægten af ith element er wi og overskuddet ved at vælge denne post er pi. Hvilke ting skal Tyven tage?,
dynamisk programmering tilgang
Lad jeg være den højest nummererede element i en optimal løsning s for dollars dollars. Så S ‘ = S – {I} er en optimal løsning for dollars-{i dollars og værdien til løsningen s er vi plus værdien af sub-problem.
Vi kan udtrykke denne kendsgerning i følgende formel: Definer c for at være løsningen for varer 1,2, … , i og den maksimale vægt w.,
Den algoritme, der tager følgende input
-
Den maksimale vægt W
-
antallet af elementer n
-
De to sekvenser v = <v1, v2, …, vn> og w = <w1, w2, …, wn>
sæt af emner at tage denne forbindelse kan ses ud fra tabellen, der starter på c, og spore bagud, hvor den optimale værdier kom fra.
analyse
denne algoritme tager times(n,)) gange som tabel c har (n + 1).(++1) poster, hvor hver post kræver time (1) tid til at beregne.,