tässä opetusohjelmassa, aiemmin olemme keskustelleet Murto-Selkäreppu ongelma käyttäen Ahne lähestymistapa. Olemme osoittaneet, että ahne lähestymistapa antaa optimaalisen ratkaisun Murtolukuihin. Tämä luku kattaa kuitenkin 0-1 Knapsack-ongelman ja sen analyysin.
0-1 Knapsackissa esineitä ei voi rikkoa, jolloin varkaan pitäisi ottaa esine kokonaisuutena tai jättää se., Tämä on syy kutsua sitä 0-1 Knapsack.
Näin ollen, siinä tapauksessa, 0-1 Repun, arvo xi voi olla joko 0 tai 1, missä muut rajoitukset pysyvät ennallaan.
0-1-osumaa ei voi ratkaista ahnaasti. Ahne lähestymistapa ei takaa optimaalista ratkaisua. Monissa tapauksissa ahne lähestymistapa voi antaa optimaalisen ratkaisun.
seuraavat esimerkit vahvistavat lausuntomme.
Esimerkki 1
mietitäänpä, että kapasiteetti reppu on W = 25 ja kohteet on esitetty seuraavassa taulukossa.,
| kohde | a | b | c | d | |
|---|---|---|---|---|---|
| voitto | 24 | 18 | 18 | 10 | |
| paino | 24 | 10 | 10 | 7 |
ottamatta huomioon yksikköpainokohtaista voittoa (pi / Wi), jos sovellamme ahnetta lähestymistapaa tämän ongelman ratkaisemiseksi, valitaan ensimmäinen erä A, koska se tuottaa suurimman mahdollisen voiton kaikkien elementtien joukossa.,
kohteen A valinnan jälkeen kohdetta ei enää valita. Näin ollen kyseisille erille kokonaisvoitto on 24. Optimaaliseen ratkaisuun päästään valitsemalla kohteita B ja C, joissa kokonaisvoitto on 18 + 18 = 36.
Example-2
sen sijaan, että kohteet valittaisiin kokonaishyödyn perusteella, tässä esimerkissä kohteet valitaan suhdeluvun pi / wi perusteella. Tarkastellaanpa, että knapsackin kapasiteetti on W = 60 ja kohteet on esitetty seuraavassa taulukossa.,
| 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., Kuitenkin, optimaalinen ratkaisu tässä tapauksessa voidaan saavuttaa valitsemalla kohteita, B ja C, joissa yhteensä voittoa on 280 + 120 = 400.
siksi voidaan päätellä, että ahne lähestymistapa ei välttämättä anna optimaalista ratkaisua.
0-1 Knapsackin ratkaisemiseen tarvitaan dynaamista Ohjelmointimenetelmää.
Ongelmalausunto
varas ryöstää kaupan ja voi kuljettaa maksimipainon W: tä reppuunsa. On n kohteita ja paino ith kohde on wi ja voitto valitsemalla tämän kohteen on pi. Mitä tavaroita varkaan tulisi ottaa?,
Dynamic-Programming Approach
let i be the highest-numered item in an optimal solution S for w dollars. Sitten S ’ = S – {i} on optimaalinen ratkaisu W-Wiin dollareille ja ratkaisun arvo s On Vi plus aliongelman arvo.
voimme ilmaista tämän tosiasian seuraavalla kaavalla: määrittele C olevan ratkaisu kohteille 1,2, … , i ja enimmäispaino w.,
algoritmi ottaa seuraavat syötöt
-
maksimipaino W
kappalemäärä n
kaksi sekvenssiä v = <v1, v2, …, vn>ja w = <W1, W2, …, WN>
taulukosta voidaan päätellä otettavien kohteiden joukko alkaen C: stä ja taaksepäin, mistä optimaaliset arvot tulivat.
Analyysi
Tämä algoritmi ottaa θ(n, w) kertaa kuin taulukossa c on (n + 1).(w + 1) merkinnät, joissa jokainen merkintä vaatii θ (1) aikaa laskea.,