Rygsækproblemet
En vandrer med en vægtgrænse, en tyv med en sæk, en virksomhed med et budget og en liste over projekter: De står alle over for det samme spørgsmål. Hvad skal med for at få mest værdi uden at gå over grænsen? Det er rygsækproblemet, og dynamisk programmering løser det præcist, når vægtene er hele tal af moderat størrelse.
Problemet
Der er n genstande, hver med en vægt og en værdi, og en rygsæk, der højst kan rumme vægten W. Vælg en mængde genstande, hvis samlede vægt højst er W, og hvis samlede værdi er så stor som muligt. Hver genstand kommer med hel eller bliver udenfor, og derfor kaldes det 0/1-rygsækproblemet. Med n genstande er der 2ⁿ mulige mængder, så det bliver hurtigt umuligt at prøve dem alle.
Tabellen
Lad best[i][w] være den største værdi, der kan være i vægten w med kun de første i genstande. Så er best[0][w] = 0, og for hver senere række er der to valg: udelad genstand i, hvilket giver best[i − 1][w], eller, hvis dens vægt wᵢ kan være der, pak den, hvilket giver dens værdi plus best[i − 1][w − wᵢ]. Den største af de to er best[i][w]. Når tabellen fyldes række for række, er begge de celler, der skal bruges, altid klar.
Et eksempel
Tag en kapacitet på 7 og fire genstande med vægtene 1, 3, 4 og 5 og værdierne 1, 4, 5 og 7. Med kun den første genstand er hver kapacitet fra 1 og op 1 værd. Når den anden kommer til, kan kapacitet 4 rumme begge for 5. Når den tredje kommer til, kan kapacitet 7 rumme genstand 2 og 3 for 9. Den fjerde genstand, med vægt 5 og værdi 7, kunne komme med sammen med genstand 1 for 8 ved kapacitet 6 eller 7, men 9 er bedre, så cellen nederst til højre er 9: pak genstandene med vægt 3 og 4.
Hvor svært er det?
Tabellen kræver omkring n·W trin. Det ser hurtigt ud, men W er et tal, og et tal med d cifre kan være så stort som 10 i d'te potens, så arbejdet vokser eksponentielt med inputtets længde. Rygsækproblemet er NP-svært; det var et af Richard Karps 21 NP-komplette problemer fra 1972. I praksis klarer tabellen, branch and bound og gode approksimationsmetoder store virkelige tilfælde godt.
Historie og anvendelser
Navnet går tilbage til matematikeren Tobias Dantzig i begyndelsen af det 20. århundrede, og hans søn George Dantzig gav en klassisk grådig metode til det i 1957. Rygsækproblemer dukker op i budgetlægning og porteføljevalg, når råmateriale skal skæres med så lidt spild som muligt, ved lastning af gods og endda i tidlig kryptografi med offentlige nøgler: Merkle–Hellman-kryptosystemet fra 1978 byggede på et rygsækproblem og blev brudt få år senere.
Udforsk det
Åbn appen, skift til visningen Tabel, og tryk på Trin. Den orange celle er ved at blive fyldt, og de blå celler er de to, den sammenligner: cellen lige ovenover og, i rækken ovenover, cellen genstandens vægt til venstre. Efter den sidste celle klatrer tilbagelæsningen op fra hjørnet nederst til højre i orange, og de pakkede genstande vises under tabellen.
Ofte stillede spørgsmål
Hvad er forskellen på 0/1-, begrænset og ubegrænset rygsækproblem?
I 0/1-versionen tages hver genstand højst én gang. I den begrænsede version findes hver genstand i et begrænset antal eksemplarer, og i den ubegrænsede version i et vilkårligt antal. Tabellen ændrer sig kun lidt mellem dem.
Er den grådige metode nogensinde rigtig for rygsækproblemet?
For det fraktionelle rygsækproblem, hvor genstande kan deles, er det optimalt at tage den bedste værdi pr. vægt først. For hele genstande kan den ramme langt ved siden af, men den bedste af den grådige løsning og den enkelte mest værdifulde genstand er altid mindst halvdelen af den bedste værdi værd.
Hvor meget hukommelse kræver tabellen?
(n + 1)·(W + 1) celler for hele tabellen, og det er det, der skal til for at læse genstandene tilbage. Hvis du kun vil have den bedste værdi, er én række med W + 1 celler nok, fyldt fra højre mod venstre.
Er rygsækproblemet det samme som delmængdesum?
Delmængdesum (subset sum) er det specialtilfælde, hvor hver genstands værdi er lig med dens vægt, og spørgsmålet er, om rygsækken kan fyldes helt præcist. Det er også NP-komplet og løses med samme slags tabel.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv rygsækproblemet