streamalism.org

1. Introduksjon

Ryggsekkproblemet er et kombinatorisk optimaliseringsproblem som har mange applikasjoner. I denne opplæringen løser vi dette problemet i Java.

2. Ryggsekkproblemet

I ryggsekkproblemet har vi et sett med ting. Hver vare har en vekt og en verdi:

Vi ønsker å legge disse artiklene i en ryggsekk. Imidlertid har den en vektgrense:

Derfor må vi velge varene hvis totale vekt ikke overstiger vektgrensen, og deres totale verdi er så høy som mulig. For eksempel er den beste løsningen for eksemplet ovenfor å velge 5 kg-varen og 6 kg-varen, noe som gir en maksimumsverdi på $ 40 innenfor vektgrensen.

Ryggsekkproblemet har flere varianter. I denne opplæringen vil vi fokusere på 0-1 ryggsekkproblemet. I 0-1-ryggsekkproblemet må hvert element enten være valgt eller etterlatt. Vi kan ikke ta en del av en vare. Vi kan heller ikke ta en vare flere ganger.

3. Matematisk definisjon

La oss nå formalisere 0-1 ryggsekkproblemet i matematisk notasjon. Gitt et sett med n gjenstander og vektgrensen W, kan vi definere optimaliseringsproblemet som:

Dette problemet er NP-vanskelig. Derfor er det ingen polynom-tidsalgoritme som løser den for øyeblikket. Imidlertid er det en pseudo-polynomial tidsalgoritme som bruker dynamisk programmering for dette problemet.

4. Rekursiv løsning

Vi kan bruke en rekursjonsformel for å løse dette problemet:

I denne formelen, M (n, w) er den optimale løsningen for n gjenstander med vektgrense w. Det er maksimum av følgende to verdier:

• Den optimale løsningen fra (n-1) gjenstander med vektgrensen w (unntatt n-te vare)
• Verdien av n-te vare pluss den optimale løsningen fra (n-1) gjenstander og w minus vekt av n-th element (inkludert n-te vare)

Hvis vekten av n-te varen er mer enn dagens vektgrense, vi inkluderer den ikke. Derfor er det i den første kategorien av de to ovennevnte tilfellene.

Vi kan implementere denne rekursjonsformelen i Java:

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

I hvert rekursjonstrinn må vi evaluere to suboptimale løsninger. Derfor er kjøretiden til denne rekursive løsningen O (2n).

5. Dynamisk programmeringsløsning

Dynamisk programmering er en strategi for linearisering av ellers eksponentielt vanskelige programmeringsproblemer. Tanken er å lagre resultatene av delproblemer slik at vi ikke trenger å beregne dem senere.

Vi kan også løse 0-1 ryggsekkproblemet med dynamisk programmering. For å bruke dynamisk programmering lager vi først en todimensjonal tabell med dimensjoner fra 0 til n og 0 til W. Deretter bruker vi en bottom-up-tilnærming for å beregne den optimale løsningen med denne tabellen:

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]; } annet {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øsningen har vi en nestet løkke over varenummeret n og vektgrensen W. Derfor er det kjøretiden O (nW).

6. Konklusjon

I denne opplæringen viste vi en matematisk definisjon av 0-1 ryggsekkproblemet. Så ga vi en rekursiv løsning på dette problemet med Java-implementering. Til slutt brukte vi dynamisk programmering for å løse dette problemet.

Som alltid er kildekoden for artikkelen tilgjengelig på GitHub.