Uppdatering: läs om optimera rymdets komplexitet i den dynamiska Programmeringslösningen i min uppföljningsartikel här.,
Ryggsäcksproblemet är ett riktigt intressant problem i kombinatoriken — för att citera Wikipedia,
”med tanke på en uppsättning objekt, var och en med en vikt och ett värde, bestämma antalet varje objekt att inkludera i en samling så att den totala vikten är mindre än eller lika med en given gräns och det totala värdet är så stort som möjligt.”
Från Wikipedia ser vi att det finns några varianter av Ryggsäcksproblemet: 0-1 ryggsäck, begränsad ryggsäck och obegränsad ryggsäck., Idag fokuserar vi på den vanligaste (och enklaste) variationen: 0-1 ryggsäcksproblemet.
en något mer intressant och relatable frasering av 0-1 ryggsäck problemet är:
överväga en tjuv kommer in i ett hem att råna och han bär en ryggsäck. Det finns fast antal objekt i hemmet — var och en med sin egen vikt och värde-smycken, med mindre vikt och högsta värde vs tabeller, med mindre värde men mycket tung. För att lägga till bränsle i elden har tjuven en gammal ryggsäck som har begränsad kapacitet., Självklart kan han inte dela bordet i hälften eller smycken i 3/4ths. Antingen tar han den eller lämnar den. Källa
tyvärr hade jag svårt att förstå vissa delar av hackerearth-artikeln, Varför jag bestämde mig för att skriva min egen artikel. Denna artikel kommer att till stor del baseras på Hackerearths artikel och kodavsnitt är skrivna i Java. Jag kommer att tacking på ytterligare förklaringar och utarbetningar där jag känner att de är nödvändiga.
Vi kommer att lösa detta problem med dynamisk programmering., Dynamisk programmering kräver en optimal understruktur och överlappande delproblem, vilka båda är närvarande i 0-1 ryggsäck problem, som vi kommer att se.
det är bra om du inte förstår vad ”optimal understruktur” och ”överlappande delproblem” är (det är en artikel för en annan dag). I huvudsak betyder det bara en viss smak av problem som gör det möjligt för oss att återanvända tidigare lösningar på mindre problem för att beräkna en lösning på det nuvarande problemet. Du får se vad jag menar om en stund.,
Problem detaljer
eftersom detta är 0-1 ryggsäck problem, vi kan antingen inkludera ett objekt i vår ryggsäck eller utesluta det, men inte inkludera en bråkdel av det, eller inkludera det flera gånger.
lösning
först skapar vi en 2-dimensionell array (dvs. en tabell) av n + 1 rader och w + 1 kolumner.
ett radnummer i representerar uppsättningen av alla objekt från rader 1-i. till exempel förutsätter värdena i rad 3 att vi bara har Objekt 1, 2 och 3.
ett kolumnnummer J representerar viktkapaciteten hos vår ryggsäck., Därför förutsätter värdena i kolumn 5 till exempel att vår ryggsäck kan hålla 5 viktenheter.
sätta ihop allt, en post i rad i, kolumn j representerar det maximala värdet som kan erhållas med objekt 1, 2, 3 … i, i en ryggsäck som kan hålla j vikt enheter.
låt oss ringa vårt bordmat för matrix. Därför int mat = new int.
steg 2:
Vi kan omedelbart börja fylla några poster i vår tabell: basfall, för vilka lösningen är trivial., Till exempel, på rad 0, när vi inte har några objekt att välja mellan, måste det maximala värdet som kan lagras i någon ryggsäck vara 0. På samma sätt, i kolumn 0, för en ryggsäck som kan hålla 0 vikt enheter, är det maximala värdet som kan lagras i det 0. (Vi antar att det inte finns några masslösa, värdefulla föremål.)
vi kan göra det med 2 för loopar:
steg 3 (problemets crux):
nu vill vi börja fylla vårt bord., Som med alla dynamiska programmeringslösningar kommer vi vid varje steg att använda oss av våra lösningar på tidigare delproblem.
Jag ska först beskriva logiken innan jag visar ett konkret exempel.
förhållandet mellan värdet på rad i, kolumn j och värdena till föregående delproblem är följande:
minns att vi vid rad i och kolumn j tar itu med ett delproblem som består av objekt 1, 2, 3 … i med en ryggsäck med J-kapacitet. Det finns 2 alternativ vid denna tidpunkt: vi kan antingen inkludera punkt i eller inte., Därför måste vi jämföra det maximala värde som vi kan få med och utan objekt i.
det maximala värde som vi kan få utan objekt i kan hittas på rad i-1, kolumn j. den här delen är lätt. Resonemanget är enkelt: oavsett det maximala värdet vi kan få med objekt 1, 2, 3 … Jag måste självklart vara samma maximala värde som vi kan få med objekt 1, 2, 3 … i – 1, Om vi väljer att inte inkludera objekt i.
för att beräkna det maximala värdet som vi kan få med objekt i måste vi först jämföra vikten av objekt i med ryggsäckens viktkapacitet., Självklart, om objektet jag väger mer än vad ryggsäcken kan hålla, kan vi inte inkludera det, så det är inte meningsfullt att utföra beräkningen. I så fall är lösningen på detta problem helt enkelt det maximala värde som vi kan få utan objekt i (dvs. värdet i raden ovan, i samma kolumn).
anta dock att objektet jag väger mindre än ryggsäckens kapacitet. Vi har således möjlighet att inkludera det, om det potentiellt ökar det maximala uppnåbara värdet., Det maximala erhållna värdet genom att inkludera punkt i är således = värdet av punkt i själv + det maximala värdet som kan erhållas med den återstående kapaciteten hos ryggsäcken. Vi vill naturligtvis till fullo utnyttja kapaciteten hos vår ryggsäck, och inte låta någon återstående kapacitet gå till spillo.
därför, vid rad i och kolumn j (som representerar det maximala värde vi kan få där), skulle vi välja antingen det maximala värde som vi kan få utan objekt i, eller det maximala värde som vi kan få med objekt i, beroende på vilket som är större.
här är ett konkret exempel på vad jag menar.,
på rad 3 (punkt 2) och kolumn 5 (punkt 2). ryggsäck kapacitet på 4), vi kan välja att antingen inkludera punkt 2 (som väger 4 enheter) eller inte. Om vi väljer att inte inkludera det är det maximala värdet vi kan få detsamma som om vi bara har Objekt 1 att välja mellan (som finns i raden ovan, dvs 0)., Om vi vill inkludera punkt 2 är det maximala värdet vi kan få med punkt 2 värdet på punkt 2 (40) + det maximala värdet vi kan få med den återstående kapaciteten (vilket är 0, eftersom ryggsäcken redan är helt full).
på rad 3 (punkt 2), och kolumn 10 (ryggsäck kapacitet på 9), igen, vi kan välja att antingen inkludera punkt 2 eller inte. Om vi väljer att inte, det maximala värdet vi kan få är densamma som i raden ovan i samma kolumn, dvs 10 (genom att endast inkludera punkt 1, som har ett värde på 10). Om vi inkluderar punkt 2 har vi en återstående ryggsäck kapacitet på 9 – 4 = 5., Vi kan ta reda på det maximala värdet som kan erhållas med en kapacitet på 5 genom att titta på raden ovan, i kolumn 5. Således är det maximala värdet vi kan få genom att inkludera punkt 2 40 (värdet av punkt 2) + 10 = 50.
vi väljer den större av 50 vs 10, och så det maximala värdet vi kan få med objekt 1 och 2, med en ryggsäck kapacitet på 9, är 50.,
algoritmen kan uttryckas i Java så här:
steg 4 (slutlösning):
när tabellen har fyllts i kan den slutliga lösningen hittas på sista raden i den sista kolumnen, som representerar det maximala värdet som kan erhållas med alla objekt och den fulla kapaciteten av ryggsäcken.
return mat;
arbetskod:
notera: här skrev jag ut det slutliga svaret istället för att returnera det, eftersom allt är inrymt under public static void main.,
Thanks for reading!