0/1 Knapsekkproblemfiks ved hjelp av dynamisk programmeringseksempel

Hva er ryggsekkproblemet?

Ocuco Rullesekk problem er et klassisk kombinatorisk optimaliseringsproblem. Et supermarked lager n pakker (n ≤ 100). Pakke i har vekt W[i] ≤ 100 og verdi V[i] ≤ 100. En tyv kan ikke bære vekt som overstiger kapasiteten M (M ≤ 100). Hvilke pakker bør tyven ta for å maksimere den totale verdien?

Inngang:

• Maksimal vekt M og antall pakker n.
• Array av vekt W[i] og tilsvarende verdi V[i].

Utgang:

• Maksimal totalverdi oppnåelig innenfor kapasiteten.
• Det nøyaktige settet med pakker tyven bør ta.

Knapsack-algoritmen deler seg inn i to kjente varianter:

• 0/1 Ryggsekkproblem løses med dynamisk programmering. Hver pakke tas enten hel eller blir liggende igjen – ingen brøkdeler og ingen duplikater.
• Problem med brøksekk løst med en grådig strategi. Her kan du ta en brøkdel av en pakke for å fylle den gjenværende kapasiteten.

Hvordan løse Knapsack-problem ved hjelp av dynamisk programmering med eksempel

Del-og-hersk-metoden deler et stort problem inn i delproblemer, og fortsetter deretter å dele opp til hvert delproblem er enkelt. Ren rekursjon løser imidlertid ofte det samme delproblemet mange ganger og er sløsing med arbeid.

Kjerneideen bak dynamisk programmering i Knapsack er å lagre alle løste delproblemer i en tabell. Gjentatte kall leser svaret i stedet for å beregne det på nytt, og gjør dermed en eksponensiell rekursjon om til polynomisk tidskode.

Løs Knapsack-problem ved hjelp av dynamisk programmering

For å designe en dynamisk programmeringsløsning følger du fire trinn:

• Løs de minste delproblemene først.
• Utled en rekursjon som bygger et delproblemsvar fra mindre regelmessigheter.
• Lagre svar på delproblemer i en tabell beregnet nedenfra og opp ved hjelp av gjentakelsen.
• Sett sammen det endelige svaret fra den fullstendig utfylte tabellen.

Analyser 0/1 ryggsekkproblemet

Den optimale verdien avhenger av to uavhengige faktorer:

1. Hvor mange pakker er fortsatt under vurdering?
2. Den gjenværende vekten kan ryggsekken fortsatt lagre.

Fordi objektivfunksjonen er avhengig av to størrelser, må tabellen med alternativer være todimensjonal. La B[i][j] betegner maksimumsverdien når man velger mellom pakker {1, …, i} med vektgrense j.

• Det endelige svaret er B[n][M], den beste totalverdien på tvers av alle n pakker under kapasitet M.
• Den totale valgte vekten er alltid begrenset av gjeldende kapasitet: B[i][j] ≤ j.

Eksempel: hvis B[4][10] = 8, er den beste totalvekten fra de fire første pakkene under kapasitet 10 8. Noen av disse fire pakkene kan hoppes over.

Formel for å beregne B[i][j]

• W[i], V[i] er vekten og verdien av pakke i, hvor i er i {1, …, n}.
• M er den maksimale vekten sekken kan bære.

Basistilfelle med én pakke: for hver kapasitet j ≥ W[1]:

B[1][j] = W[1]

For det generelle tilfellet, avgjør om pakke i skal inkluderes under kapasitet j:

• Hvis pakke i er hoppet, B[i][j] er lik den beste verdien ved bruk av pakker {1, …, i-1} under kapasitet j:

B[i][j] = B[i - 1][j]

• Hvis pakke i er tatt (kun tillatt når W[i] ≤ j), B[i][j] er lik V[i] pluss den beste verdien fra pakkene {1, …, i-1} under kapasitet j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Ta den største av de to kandidatene.

Grunnlag for dynamisk programmering

Å kombinere de to tilfellene gir full gjentakelse:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Basistilfellet er B[0][j] = 0 for hver j, fordi null pakker gir null verdi uavhengig av kapasitet.

Beregn alternativtabellen

Bygg B ved hjelp av gjentakelsen. Når B er fylt, driver den samme tabellen trace-back som rekonstruerer de valgte pakkene. Tabell B har n + 1 rader og M + 1 kolonner:

• Rad 0 er basistilfellet, fylt med nuller.
• Bruk rad 0 til å beregne rad 1, rad 1 til å beregne rad 2, og fortsett til rad n er fullført.

Tabell over alternativer

Trace

Når B er ferdig, fokuser på B[n][M], den optimale totalverdien på tvers av alle n pakker med kapasitet M.

• If B[n][M] = B[n-1][M], pakke n ble ikke valgt, så fortsett tracfra B[n-1][M].
• If B[n][M] ≠ B[n-1][M], pakke n ble valgt, så fortsett tracfra B[n-1][M – W[n]].

Gjenta til du kommer til rad 0 i tabellen.

Algoritme for å slå opp alternativtabellen for å finne de valgte pakkene

Merk: når som helst B[i][j] = B[i-1][j], pakke i er ikke valgt. Verdien B[n][M] er den optimale totalverdien pakket i ryggsekken.

Trinn for tracde valgte pakkene:

• Trinn 1: Start ved i = n, j = M.
• Trinn 2: Skann kolonne j nedenfra og opp til du finner en rad i der B[i][j] > B[i-1][j]. Merk pakke i som valgt: Select[i] = true.
• Trinn 3: Oppdater j = j – W[i]. Hvis j > 0, gå tilbake til trinn 2, ellers gå til trinn 4.
• Trinn 4: Skriv ut alle pakker som er merket som valgt.

Java Code

Følgende Java metoden fyller B[][] nedenfra og opp, skriver ut tabellen for inspeksjon, og deretter tracde valgte pakkene.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Funksjon knapsackDyProg() i Java

Forklaring av koden:

1. Tildel tabell B[][] og initialiser hver celle til 0.
2. Fyll B[][] nedenfra og opp ved å bruke gjentakelsen fra forrige avsnitt.
3. Start hver celle med verdien «hopp over pakke i» B[i-1][j].
4. Hvis det er mulig å velge pakke i og gir en strengt tatt bedre verdi, overskriv cellen.
5. TracFlytt de valgte elementene fra rad n tilbake til rad 0.
6. Når pakke n velges, reduser den gjenværende kapasiteten med W[n-1].

Rettingsmerknad: den opprinnelige kodebitens muterte parameter M mens de fortsatt leser B[n][M]Den sikrere versjonen ovenfor bruker en separat markør. j for trace.

Ocuco Java driveren kjører algoritmen på to utarbeidede eksempler:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Utdata for det første eksemplet:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Utdata for det andre eksemplet:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Tids- og romkompleksiteten til 0/1 ryggsekk

• Tidskompleksitet: O(n · M) — de to nestede løkkene feier n elementer over M+1 kapasitetstilstander.
• Romkompleksitet: O(n · M) for hele tabellen, reduserbar til O(M) ved keeping bare forrige rad når trace-back er ikke nødvendig.

Kjøretiden er pseudo-polynom: polynom i verdien av M, men eksponensiell i bitene som brukes til å kode M. Det er derfor 0/1 Knapsack forblir NP-hard selv om dynamisk programmering er effektivt i praksis.

Anvendelser av 0/1-ryggsekkproblemet

• Lasting av gods, pakking av containere og plukking på lager under vektbegrensninger.
• Budsjettfordeling på tvers av investeringsprosjekter med faste kostnader og forventet avkastning.
• Problemer med lagerbeholdning i produksjonen som ikke kan dele individuelle deler.
• Kryptografiske ordninger som Merkle-Hellman som bygger på ryggsekkhardhet.
• Ressursbegrenset planlegging i skytjenester og plassering av CPU-oppgaver.
• Funksjonsvalg i maskinlæring under et fast funksjonsbudsjett.

Spørsmål og svar