in deze tutorial hebben we eerder fractioneel gesproken knapzak probleem met behulp van hebzuchtige aanpak. We hebben aangetoond dat hebzuchtige aanpak een optimale oplossing biedt voor fractionele Ransel. Dit hoofdstuk zal echter 0-1 Knapzak probleem en de analyse ervan te behandelen.
in 0-1 Ransel kunnen items niet worden gebroken, wat betekent dat de dief het item als geheel moet nemen of moet verlaten., Dit is de reden achter het noemen van het als 0-1 Ransel.
in het geval van 0-1 Ransel kan de waarde van xi dus 0 of 1 zijn, waarbij andere beperkingen hetzelfde blijven.
0-1 Knapzak kan niet worden opgelost door hebzuchtige aanpak. Hebzuchtige aanpak zorgt niet voor een optimale oplossing. In veel gevallen, hebzuchtige aanpak kan een optimale oplossing te geven.
de volgende voorbeelden geven ons statement weer.
Voorbeeld-1
De capaciteit van de rangeerrug is W = 25 en de items zijn zoals weergegeven in de volgende tabel.,
| Item | A | B | C | D |
|---|---|---|---|---|
| Winst | 24 | 18 | 18 | 10 |
| Gewicht | 24 | 10 | 10 | 7 |
Zonder rekening te houden van de winst per eenheid gewicht (pi/wi), als we Hebberig aanpak voor het oplossen van dit probleem, is het eerste item wordt geselecteerd als het zal bijdragen maximale winst tussen alle elementen.,
na het selecteren van item A zal geen item meer worden geselecteerd. Vandaar, voor deze gegeven reeks posten totale winst is 24. Terwijl, de optimale oplossing kan worden bereikt door het selecteren van items, B en C, waar de totale winst is 18 + 18 = 36.
Voorbeeld-2
in plaats van de items te selecteren op basis van het totale voordeel, worden in dit voorbeeld de items geselecteerd op basis van ratio pi/wi. Laten we bedenken dat de capaciteit van de ransel is w = 60 en de items zijn zoals weergegeven in de volgende 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., Echter, de optimale oplossing van deze instantie kan worden bereikt door het selecteren van items, B en C, waar de totale winst is 280 + 120 = 400.
derhalve kan worden geconcludeerd dat hebzuchtige benadering mogelijk geen optimale oplossing biedt.
om 0-1 Knapzak op te lossen, is een dynamische Programmeerbenadering vereist.
Probleemstatement
een dief berooft een winkel en kan een maximaal gewicht van W in zijn ransel dragen. Er zijn N items en het gewicht van ith item is wi en de winst van het selecteren van dit item is pi. Welke items moet de dief nemen?,
dynamische Programmeerbenadering
laat i het hoogst genummerde item zijn in een optimale oplossing S voor W dollars. Dan is S ‘ = S – {i} een optimale oplossing voor W-Wi dollars en de waarde voor de oplossing S is Vi plus de waarde van het subprobleem.
We kunnen dit feit in de volgende formule uitdrukken: definieer c als de oplossing voor items 1,2, … , i en het maximumgewicht w.,
Het algoritme zijn de volgende ingangen
-
Het maximale gewicht W
-
Het aantal items n
-
De twee sequenties v = <v1, v2, …, vn> en w = <w1, w2, …, wn>
De set items te nemen, kan worden afgeleid uit de tabel, te beginnen bij c & tracing naar achteren waar de optimale waarden vandaan kwam.
analyse
dit algoritme neemt θ (n, w) keer als tabel c heeft (n + 1).(w + 1) vermeldingen, waarbij elke vermelding θ (1) tijd nodig heeft om te berekenen.,