update: lees hier over het optimaliseren van de ruimtecomplexiteit van de dynamische programmeeroplossing in mijn vervolgartikel.,
Het Knapzak-probleem is een heel interessant probleem in de combinatoriek-om Wikipedia aan te halen, bepaalt
“gegeven een verzameling items, elk met een gewicht en een waarde, het aantal van elk item dat in een verzameling moet worden opgenomen, zodat het totale gewicht kleiner is dan of gelijk is aan een bepaalde limiet en de totale waarde zo groot mogelijk is.”
van Wikipedia zien we dat er een paar variaties zijn van het Knapzak probleem: 0-1 knapzak, bounded knapzak, en unbounded knapzak., Vandaag richten we ons op de meest voorkomende (en eenvoudigste) variatie: het 0-1 ranselprobleem.
een iets interessantere en meer relateerbare frasering van het 0-1 knapzak probleem is:
beschouw een dief krijgt in een huis om te beroven en hij draagt een ranpack. Er zijn vast aantal items in het huis-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 sieraden in 3/4. Hij neemt het of laat het achter. Source
helaas had ik moeite met het begrijpen van sommige delen van het Hackerearth artikel, daarom besloot ik mijn eigen artikel te schrijven. Dit artikel zal grotendeels worden gebaseerd op artikel Hackerearth ‘ s en code fragmenten zijn geschreven in Java. Ik zal aanvullende verklaringen en uitwerkingen volgen waar ik denk dat ze nodig zijn.
We zullen dit probleem oplossen met dynamisch programmeren., Dynamisch programmeren vereist een optimale onderstructuur en overlappende subproblemen, die beide aanwezig zijn in het 0-1 ranselprobleem, zoals we zullen zien.
Het is prima als je niet begrijpt wat “optimale substructuur” en “overlappende subproblemen” zijn (dat is een artikel voor een andere dag). In wezen betekent het gewoon een bepaalde smaak van problemen die ons in staat stellen om eerdere oplossingen voor kleinere problemen te hergebruiken om een oplossing voor het huidige probleem te berekenen. Je zult zien wat ik bedoel.,
Probleemdetails
aangezien dit het 0-1 knapzak-probleem is, kunnen we een item in onze ransel opnemen of uitsluiten, maar er geen fractie van opnemen, of het meerdere keren opnemen.
oplossing
eerst maken we een 2-dimensionale array (d.w.z. een tabel) van n + 1 rijen en w + 1 kolommen.
een rijnummer i vertegenwoordigt de verzameling van alle items uit rijen 1-i. bijvoorbeeld, de waarden in rij 3 gaan ervan uit dat we alleen items 1, 2 en 3 hebben.
een kolomnummer j staat voor het gewicht van onze ransel., Daarom gaan de waarden in kolom 5 er bijvoorbeeld van uit dat onze ransel 5 gewichtseenheden kan bevatten.
alles samenvoegen, een item in rij i, kolom j vertegenwoordigt de maximale waarde die kan worden verkregen met de items 1, 2, 3 … i, in een rugzak die j gewichtseenheden kan bevatten.
laten we onze tabel mat voor matrix aanroepen. Daarom is int mat = new int.
Stap 2:
We kunnen onmiddellijk beginnen met het invullen van enkele regels in onze tabel: de basiscases, waarvoor de oplossing triviaal is., Bijvoorbeeld, bij rij 0, wanneer we geen items hebben om uit te kiezen, moet de maximale waarde die in een ransel kan worden opgeslagen 0 zijn. Evenzo, bij kolom 0, voor een ransel die 0 gewichtseenheden kan bevatten, is de maximale waarde die erin kan worden opgeslagen 0. (We gaan ervan uit dat er geen massaloze, waardevolle items.)
We kunnen dit doen met 2 voor loops:
Stap 3 (de kern van het probleem):
nu willen we beginnen met het invullen van onze tabel., Zoals bij alle dynamische programmeeroplossingen, maken we bij elke stap gebruik van onze oplossingen voor eerdere subproblemen.
Ik zal eerst de logica beschrijven, voordat ik een concreet voorbeeld laat zien.
de relatie tussen de waarde in rij i, kolom j en de waarden ten opzichte van de vorige subproblemen is als volgt:
bedenk dat we op rij i en kolom j een subprobleem aanpakken dat bestaat uit de punten 1, 2, 3 … i met een rugzak van J-capaciteit. Er zijn 2 opties op dit punt: we kunnen item i of niet opnemen., Daarom moeten we de maximale waarde vergelijken die we kunnen verkrijgen met en zonder item i.
De maximale waarde die we kunnen verkrijgen zonder item i is te vinden in rij i-1, kolom j. dit deel is eenvoudig. De redenering is eenvoudig: welke maximale waarde we ook kunnen verkrijgen met de items 1, 2, 3 … Ik moet uiteraard dezelfde maximale waarde zijn die we kunnen verkrijgen met de items 1, 2, 3 … i – 1, als we ervoor kiezen om item i niet op te nemen.
om de maximale waarde te berekenen die we kunnen verkrijgen met item i, moeten we eerst het gewicht van item i vergelijken met het gewicht van de rugzak., Natuurlijk, als item I weegt meer dan wat de ransel kan houden, kunnen we het niet opnemen, dus het heeft geen zin om de berekening uit te voeren. In dat geval is de oplossing voor dit probleem gewoon de maximale waarde die we kunnen verkrijgen zonder item i (dat wil zeggen de waarde in de rij hierboven, in dezelfde kolom).
echter, stel dat item i minder weegt dan de capaciteit van de ransel. We hebben dus de mogelijkheid om het op te nemen, als het potentieel de maximaal haalbare waarde verhoogt., De maximaal haalbare waarde door item i op te nemen is dus = de waarde van item i zelf + de maximale waarde die kan worden verkregen met de resterende capaciteit van de ransel. We willen natuurlijk de capaciteit van onze ransel volledig benutten en geen resterende capaciteit laten verloren gaan.
daarom zouden we in rij i en kolom j (die de maximale waarde vertegenwoordigt die we daar kunnen verkrijgen) ofwel de maximale waarde kiezen die we zonder item i kunnen verkrijgen, ofwel de maximale waarde die we met item i kunnen verkrijgen, afhankelijk van wat groter is.
Hier is een concreet voorbeeld van wat ik bedoel.,
bij rij 3 (item 2) en kolom 5 (rugzak capaciteit van 4), kunnen we kiezen om item 2 (dat 4 eenheden weegt) of niet op te nemen. Als we ervoor kiezen om het niet op te nemen, is de maximale waarde die we kunnen verkrijgen hetzelfde als wanneer we alleen item 1 hebben om uit te kiezen (dat is te vinden in de rij hierboven, dat wil zeggen 0)., Als we item 2 willen opnemen, is de maximale waarde die we met item 2 kunnen verkrijgen de waarde van item 2 (40) + de maximale waarde die we kunnen verkrijgen met de resterende capaciteit (die 0 is, omdat de ransel al volledig vol is).
op rij 3 (item 2), en kolom 10 (rugzakcapaciteit van 9), kunnen we opnieuw kiezen om item 2 of niet op te nemen. Als we ervoor kiezen om dit niet te doen, is de maximale waarde die we kunnen verkrijgen dezelfde als die in de rij hierboven in dezelfde kolom, dat wil zeggen 10 (door alleen item 1 op te nemen, dat een waarde van 10 heeft). Als we item 2 opnemen, hebben we een resterende rugzak capaciteit van 9 – 4 = 5., We kunnen de maximale waarde die kan worden verkregen met een capaciteit van 5 achterhalen door te kijken naar de rij hierboven, in kolom 5. Dus, de maximale waarde die we kunnen verkrijgen door item 2 op te nemen is 40 (de waarde van item 2) + 10 = 50.
We kiezen de grootste van 50 vs 10, en dus is de maximale waarde die we kunnen verkrijgen met items 1 en 2, met een rugzakcapaciteit van 9, 50.,
Het algoritme kan als volgt in Java worden uitgedrukt:
Stap 4 (eindoplossing):
zodra de tabel is ingevuld, kan de eindoplossing worden gevonden op de laatste rij in de laatste kolom, die de maximale haalbare waarde vertegenwoordigt met alle items en de volledige capaciteit van de ransel.
return mat;
werkcode:
opmerking: hier heb ik het definitieve antwoord afgedrukt in plaats van het terug te geven, omdat alles onder publieke static void main staat.,
Thanks for reading!