streamalism.org

1. Introduktion

Rygsækproblemet er et kombinatorisk optimeringsproblem, der har mange applikationer. I denne vejledning løser vi dette problem i Java.

2. Rygsækproblemet

I rygsækproblemet har vi et sæt varer. Hver vare har en vægt og en værdi:

Vi vil lægge disse genstande i en rygsæk. Det har dog en vægtgrænse:

Derfor er vi nødt til at vælge de varer, hvis samlede vægt ikke overstiger vægtgrænsen, og deres samlede værdi er så høj som muligt. For eksempel er den bedste løsning til ovenstående eksempel at vælge varen på 5 kg og 6 kg, hvilket giver en maksimumsværdi på $ 40 inden for vægtgrænsen.

Rygsækproblemet har flere variationer. I denne vejledning vil vi fokusere på 0-1-rygproblemet. I 0-1-rygsækproblemet skal hver vare enten vælges eller efterlades. Vi kan ikke tage en del af en vare. Vi kan heller ikke tage en vare flere gange.

3. Matematisk definition

Lad os nu formalisere 0-1-rygsækproblemet i matematisk notation. Fik et sæt n varer og vægtgrænsen W, kan vi definere optimeringsproblemet som:

Dette problem er NP-hårdt. Derfor er der ingen polynomialtidsalgoritme, der løser den i øjeblikket. Der er dog en pseudo-polynomial tidsalgoritme, der bruger dynamisk programmering til dette problem.

4. Rekursiv løsning

Vi kan bruge en rekursionsformel til at løse dette problem:

I denne formel M (n, w) er den optimale løsning til n genstande med en vægtgrænse w. Det er det maksimale af følgende to værdier:

• Den optimale løsning fra (n-1) varer med vægtgrænsen w (undtagen n-th vare)
• Værdien af n-te vare plus den optimale løsning fra (n-1) genstande og w minus vægt af n-th element (inklusive n-th vare)

Hvis vægten af n-de vare er mere end den nuværende vægtgrænse, vi inkluderer den ikke. Derfor er det i den første kategori af de ovennævnte to tilfælde.

Vi kan implementere denne rekursionsformel i Java:

int knapsackRec (int [] w, int [] v, int n, int W) {if (n W) {return knapsackRec (w, v, n - 1, W); } andet {returner Math.max (knapsackRec (w, v, n - 1, W), v [n - 1] + knapsackRec (w, v, n - 1, W - w [n - 1])); }} 

I hvert rekursionstrin skal vi evaluere to suboptimale løsninger. Derfor er kørselstiden for denne rekursive løsning O (2n).

5. Dynamisk programmeringsløsning

Dynamisk programmering er en strategi til linearisering af ellers eksponentielt vanskelige programmeringsproblemer. Ideen er at gemme resultaterne af delproblemer, så vi ikke behøver at genberegne dem senere.

Vi kan også løse 0-1-rygsækproblemet med dynamisk programmering. For at bruge dynamisk programmering opretter vi først en 2-dimensionel tabel med dimensioner fra 0 til n og 0 til W. Derefter bruger vi en bottom-up-tilgang til at beregne den optimale løsning med denne tabel:

int knapsackDP (int [] w, int [] v, int n, int W) {if (n <= 0 || W <= 0) {return 0; } int [] [] m = ny int [n + 1] [W + 1]; for (int j = 0; j <= W; j ++) {m [0] [j] = 0; } for (int i = 1; i <= n; i ++) {for (int j = 1; j j) {m [i] [j] = m [i - 1] [j]; } andet {m [i] [j] = Math.max (m [i - 1] [j], m [i - 1] [j - w [i - 1]] + v [i - 1]); }}} returner m [n] [W]; } 

I denne løsning har vi en indlejret løkke over varenummeret n og vægtgrænsen W. Derfor er det kørt tid O (nW).

6. Konklusion

I denne vejledning viste vi en matematisk definition af 0-1 rygsækproblemet. Derefter leverede vi en rekursiv løsning på dette problem med Java-implementering. Endelig brugte vi dynamisk programmering til at løse dette problem.

Som altid er kildekoden til artiklen tilgængelig på GitHub.