Het Ranselprobleem
Ik vond het Ranselprobleem tegelijkertijd lastig en interessant. Ik ben er zeker van dat als u deze pagina bezoekt, u het probleemstatement al kent, maar alleen voor de voltooiing :
probleem:
gegeven een Rangeerzak met een maximale capaciteit van W en N items elk met zijn eigen waarde en gewicht, gooi items in de Rangeerzak zodanig dat de uiteindelijke inhoud de maximale waarde heeft. Jakkes !!,
Hier is de algemene manier waarop het probleem wordt uitgelegd – overweeg een dief krijgt in een huis om te beroven en hij draagt een ransel. Er zijn vast aantal items in de woning-elk met zijn eigen gewicht en waarde – sieraden, met minder gewicht en hoogste waarde vs tafels, met minder waarde, maar veel zwaar. Om brandstof aan het vuur toe te voegen, heeft de dief een oude ransel met beperkte capaciteit. Hij kan de tafel niet in tweeën splitsen of juwelen in 3/4., Hij neemt het of laat het achter
voorbeeld:
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}
een vluchtige blik op de voorbeeldgegevens vertelt ons dat de maximale waarde die we met de limiet van maximaal gewicht van 10 zouden kunnen bereiken 50 + 40 = 90 is met een gewicht van 7.
aanpak:
de manier waarop dit optimaal wordt opgelost, is door gebruik te maken van dynamisch programmeren – oplossen voor kleinere sets van knapzak problemen en ze vervolgens uit te breiden voor het grotere probleem.,
laten we een Item x Weight array bouwen genaamd V (Value array):
V = 4 rows * 10 columnselk van de waarden in deze matrix vertegenwoordigt een kleiner probleem.
basisgeval 1: Laten we het geval van de 0De kolom nemen. Het betekent gewoon dat de ransel 0 capaciteit heeft. Wat kun je erin houden? Niets. Dus, laten we ze allemaal vullen met 0s.
basisgeval 2: Laten we het geval van Rij 0 nemen. Het betekent gewoon dat er geen items in het huis. Wat heb je wel in je ransel als er geen items zijn. Weer niets !!! Allemaal nullen.,
oplossing:
1) nu, laten we beginnen met het invullen van de array rij-wise. Wat betekenen rij 1 en kolom 1? Dat gegeven het eerste item (rij), kunt u het in de ransel met capaciteit 1 (kolom). Nope. Het gewicht van het eerste item is 5. Dus, laten we 0 invullen. In feite zouden we niet in staat zijn om iets in te vullen totdat we de kolom 5 (Gewicht 5) bereiken.
2) Zodra we kolom 5 (die gewicht 5 vertegenwoordigt) op de eerste rij bereiken, betekent dit dat we item 1 kunnen aanpassen., Laten we hier 10 invullen (onthoud, dit is een waarde-array):
3) verder gaan, voor gewicht 6 (kolom 6), kunnen we iets anders met het resterende gewicht van 1 (gewicht – gewicht van dit item => 6 – 5). Vergeet niet, we zijn bij het eerste item. Dus, het is een soort van intuïtief dat de rest van de rij zal gewoon dezelfde waarde te zijn, omdat we niet in staat zijn om toe te voegen in een ander item voor dat extra gewicht dat we hebben.,
4) dus, het volgende interessante ding gebeurt wanneer we de kolom 4 in de derde rij bereiken. Het huidige loopgewicht is 4.
We moeten controleren op de volgende gevallen.
1) kunnen we Item 2 Aanpassen – Ja, dat kunnen we. Het gewicht van punt 2 is 4.
2) is de waarde voor het huidige gewicht hoger zonder Item 2? – Controleer de vorige rij op hetzelfde gewicht. Nope. de vorige rij * heeft 0 in het, omdat we niet in staat waren in staat om Item 1 in gewicht 4.
3) kunnen we twee items in hetzelfde gewicht plaatsen zodat we de waarde kunnen maximaliseren? – Nee., Het resterende gewicht na aftrek van het gewicht van Item2 is 0.
waarom vorige rij?
simpelweg omdat de vorige rij bij Gewicht 4 zelf een kleinere ranseloplossing is die de maximale waarde geeft die voor dat gewicht tot dat punt kan worden verzameld (door de items).,
voorbeeld,
1) de waarde van de huidige post = 40
2) het gewicht van de huidige post = 4
3) het gewicht dat overblijft = 4 – 4 = 0
4) Controleer de rij hierboven (het Item hierboven in het geval van Item 1 of de cumulatieve maximumwaarde in het geval van de rest van de rijen). Voor het resterende Gewicht 0, zijn we in staat om Item 1? Simpel gezegd, is er enige waarde in de rij hierboven voor het gegeven gewicht?,
De berekening gaat als volgt:
1) Neem de maximale waarde voor hetzelfde gewicht zonder dit item:
previous row, same weight = 0=> V2) Neem de waarde van het huidige item + waarde die we met het resterende gewicht zouden kunnen opnemen:
Max tussen de twee is 40 (0 en 40).
3) de volgende en belangrijkste gebeurtenis vindt plaats in kolom 9 en rij 2. Dat betekent dat we een gewicht van 9 hebben en we hebben twee items. Kijkend naar de voorbeeldgegevens konden we de eerste twee items huisvesten., Hier beschouwen we weinig dingen:
- de waarde van het huidige item = 40
- het gewicht van het huidige item = 4
- het gewicht dat overblijft = 9 – 4 = 5
- controleer de rij hierboven. Bij het resterende gewicht 5, zijn we in staat om Item 1.
Dus de berekening is :
1) Neem de max waarde voor hetzelfde gewicht zonder dit item:
previous row, same weight = 102) de waarde van het huidige item + waarde die we kunnen verzamelen met het resterende gewicht:
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.,
aan het einde van het oplossen van al deze kleinere problemen, hoeven we alleen maar de waarde te retourneren bij V – Item 4 bij Gewicht 10:
complexiteit
analyse van de complexiteit van de oplossing is vrij eenvoudig. We hebben gewoon een lus voor W binnen een lus van N => O (NW)
implementatie:
Hier komt de verplichte implementatiecode in Java: