Kappsäcksproblemet
En vandrare med en viktgräns, en tjuv med en säck, ett företag med en budget och en lista med projekt: alla står inför samma fråga. Vad ska med för att få mest värde utan att gå över gränsen? Det är kappsäcksproblemet, och dynamisk programmering löser det exakt när vikterna är heltal av måttlig storlek.
Problemet
Det finns n föremål, vart och ett med en vikt och ett värde, och en ryggsäck som rymmer högst vikten W. Välj en mängd föremål vars sammanlagda vikt är högst W och vars sammanlagda värde är så stort som möjligt. Varje föremål kommer med helt eller stannar utanför, och därför kallas det 0/1-kappsäcksproblemet. Med n föremål finns det 2ⁿ möjliga mängder, så att pröva alla blir snart omöjligt.
Tabellen
Låt best[i][w] vara det största värdet som får plats i vikten w med bara de i första föremålen. Då är best[0][w] = 0, och för varje senare rad finns två val: lämna föremål i utanför, vilket ger best[i − 1][w], eller, om dess vikt wᵢ får plats, packa det, vilket ger dess värde plus best[i − 1][w − wᵢ]. Det större av de två är best[i][w]. När tabellen fylls rad för rad är båda cellerna som behövs alltid klara.
Ett exempel
Ta kapaciteten 7 och fyra föremål med vikterna 1, 3, 4 och 5 och värdena 1, 4, 5 och 7. Med bara det första föremålet är varje kapacitet från 1 och uppåt värd 1. När det andra läggs till kan kapacitet 4 rymma båda för 5. När det tredje läggs till kan kapacitet 7 rymma föremål 2 och 3 för 9. Det fjärde föremålet, vikt 5 och värde 7, skulle kunna följa med föremål 1 för 8 vid kapacitet 6 eller 7, men 9 är bättre, så cellen längst ned till höger är 9: packa föremålen med vikt 3 och 4.
Hur svårt är det?
Tabellen behöver ungefär n·W steg. Det ser snabbt ut, men W är ett tal, och ett tal med d siffror kan vara så stort som 10 upphöjt till d, så arbetet växer exponentiellt med indatats längd. Kappsäcksproblemet är NP-svårt; det var ett av Richard Karps 21 NP-fullständiga problem från 1972. I praktiken klarar tabellen, branch and bound och bra approximationsscheman stora verkliga fall väl.
Historia och användning
Namnet går tillbaka till matematikern Tobias Dantzig i början av 1900-talet, och hans son George Dantzig gav en klassisk girig metod för det 1957. Kappsäcksproblem dyker upp i budgetering och portföljval, när råmaterial ska skäras med så lite spill som möjligt, vid lastning av gods och till och med i tidig kryptografi med publika nycklar: Merkle–Hellman-kryptosystemet från 1978 byggde på ett kappsäcksproblem och knäcktes några år senare.
Utforska det
Öppna appen, byt till vyn Tabell och tryck på Steg. Den orange cellen håller på att fyllas, och de blå cellerna är de två den jämför: cellen direkt ovanför och, i raden ovanför, cellen föremålets vikt åt vänster. Efter den sista cellen klättrar bakåtläsningen uppåt i orange från hörnet längst ned till höger, och de packade föremålen visas under tabellen.
Ofta ställda frågor
Vad är skillnaden mellan 0/1-, begränsat och obegränsat kappsäcksproblem?
I 0/1-versionen tas varje föremål högst en gång. I den begränsade versionen har varje föremål ett begränsat antal exemplar, och i den obegränsade hur många som helst. Tabellen ändras bara lite mellan dem.
Blir den giriga metoden någonsin rätt för kappsäcksproblemet?
För det fraktionella kappsäcksproblemet, där föremål kan delas, är det optimalt att ta bästa värdet per vikt först. För hela föremål kan den hamna långt fel, även om det bästa av den giriga lösningen och det enskilt mest värdefulla föremålet alltid är värt minst hälften av bästa värdet.
Hur mycket minne behöver tabellen?
(n + 1)·(W + 1) celler för hela tabellen, vilket är vad som behövs för att läsa bakåt fram föremålen. Om bara bästa värdet behövs räcker en rad med W + 1 celler, som fylls från höger till vänster.
Är kappsäcksproblemet samma sak som delmängdssumma?
Delmängdssumma (subset sum) är specialfallet där varje föremåls värde är lika med dess vikt och frågan är om ryggsäcken kan fyllas exakt. Det är också NP-fullständigt och löses med samma sorts tabell.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova kappsäcksproblemet