0/1 Knapsack Problem Fix ved hjælp af dynamisk programmeringseksempel

Hvad er rygsækproblemet?

Rullesæk problem er et klassisk kombinatorisk optimeringsproblem. Et supermarked n pakker (n ≤ 100). Pakke i har vægt W[i] ≤ 100 og værdi V[i] ≤ 100. En tyv kan ikke bære vægt, der overstiger kapaciteten M (M ≤ 100). Hvilke pakker skal tyven tage for at maksimere den samlede værdi?

Input:

• Maksimal vægt M og antallet af pakker n.
• Array af vægt W[i] og tilsvarende værdi V[i].

Output:

• Maksimal samlet værdi, der kan opnås inden for kapaciteten.
• Det præcise sæt pakker, som tyven skal tage.

Knapsack-algoritmen opdeles i to velkendte varianter:

• 0/1 Rygsækproblem løses ved dynamisk programmering. Hver pakke tages enten hel eller efterlades — ingen brøkdele og ingen dubletter.
• Fractional Napsack Problem løst med en grådig strategi. Her kan du tage en brøkdel af enhver pakke for at fylde den resterende kapacitet.

Sådan løses knapsækproblem ved hjælp af dynamisk programmering med eksempel

Del-og-hersk-metoden opdeler et stort problem i delproblemer og fortsætter derefter med at opdele, indtil hvert delproblem er let. Almindelig rekursion løser dog ofte det samme delproblem mange gange og spilder arbejde.

Kernidéen bag Knapsack Dynamic Programming er at gemme alle løste delproblemer i en tabel. Gentagne kald læser svaret i stedet for at genberegne det, hvilket omdanner en eksponentiel rekursion til polynomialtidskode.

Løs Knapsack-problem ved hjælp af dynamisk programmering

For at designe en dynamisk programmeringsløsning skal du følge fire trin:

• Løs de mindste delproblemer først.
• Udled en gentagelse, der opbygger et svar på et delproblem ud fra mindre gentagelser.
• Gem svar på delproblemer i en tabel beregnet bottom-up ved hjælp af gentagelsen.
• Saml det endelige svar ud fra den fuldt udfyldte tabel.

Analyser 0/1 Rullesæk-problemet

Den optimale værdi afhænger af to uafhængige faktorer:

1. Hvor mange pakker er stadig under overvejelse.
2. Den resterende vægt kan rygsækken stadig opbevare.

Da objektivfunktionen afhænger af to størrelser, skal tabellen over muligheder være todimensionel. Lad B[i][j] betegner den maksimale værdi ved valg mellem pakker {1, …, i} med vægtgrænse j.

• Det endelige svar er B[n][M], den bedste samlede værdi på tværs af alle n pakker under kapacitet M.
• Den samlede valgte vægt er altid begrænset af den aktuelle kapacitet: B[i][j] ≤ j.

Eksempel: Hvis B[4][10] = 8, er den bedste samlede vægt fra de første fire pakker under kapacitet 10 8. Nogle af disse fire pakker kan springes over.

Formel til at beregne B[i][j]

• W[i], V[i] er vægten og værdien af ​​pakke i, hvor i er i {1, …, n}.
• M er den maksimale vægt, som rygsækken kan bære.

Basistilfælde med én pakke: for hver kapacitet j ≥ W[1]:

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

I det generelle tilfælde skal du beslutte, om pakke i skal inkluderes under kapacitet j:

• Hvis pakke i er sprunget, B[i][j] er lig med den bedste værdi ved brug af pakker {1, …, i-1} under kapacitet j:

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

• Hvis pakke i er taget (kun tilladt når W[i] ≤ j), B[i][j] er lig med V[i] plus den bedste værdi fra pakkerne {1, …, i-1} under kapacitet j – W[i]:

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

Tag den største af de to kandidater.

Grundlag for dynamisk programmering

Kombination af de to tilfælde giver den fulde gentagelse:

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

Basisscenariet er B[0][j] = 0 for hvert j, fordi nul pakker giver nul værdi uanset kapacitet.

Beregn tabellen over muligheder

Byg B ved hjælp af gentagelsen. Når B er udfyldt, driver den samme tabel trace-back, der rekonstruerer de valgte pakker. Tabel B har n + 1 rækker og M + 1 kolonner:

• Række 0 er basisscenariet, udfyldt med nuller.
• Brug række 0 til at beregne række 1, række 1 til at beregne række 2, og fortsæt indtil række n er færdig.

Tabel over muligheder

Trace

Når B er færdig, fokuser på B[n][M], den optimale samlede værdi på tværs af alle n pakker med kapacitet M.

• If B[n][M] = B[n-1][M], pakke n blev ikke valgt, så fortsæt tracfra B[n-1][M].
• If B[n][M] ≠ B[n-1][M], pakke n blev valgt, så fortsæt tracfra B[n-1][M – W[n]].

Gentag indtil du når række 0 i tabellen.

Algoritme til at slå op i oversigten over muligheder for at finde de valgte pakker

Bemærk: når som helst B[i][j] = B[i-1][j], pakke i er ikke valgt. Værdien B[n][M] er den optimale samlede værdi pakket i rygsækken.

Trin til tracde valgte pakker:

• Trin 1: Start ved i = n, j = M.
• Trin 2: Scan kolonne j nedefra og op, indtil du finder række i, hvor B[i][j] > B[i-1][j]. Marker pakke i som valgt: Select[i] = true.
• Trin 3: Opdater j = j – W[i]. Hvis j > 0, gå tilbage til trin 2, ellers gå til trin 4.
• Trin 4: Udskriv alle pakker, der er markeret som valgt.

Java Code

Følgende Java Metoden udfylder B[][] bottom-up, udskriver tabellen til inspektion, og derefter tracde valgte pakker.

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--;
    }
}

Funktion knapsackDyProg() i Java

Forklaring af koden:

1. Alloker tabel B[][] og initialiser hver celle til 0.
2. Udfyld B[][] nedefra og op ved hjælp af gentagelsen fra forrige afsnit.
3. Start hver celle med værdien "skip pakke i" B[i-1][j].
4. Hvis det er muligt at vælge pakke i og giver en strengt taget bedre værdi, skal cellen overskrives.
5. TracFlyt de valgte elementer fra række n tilbage til række 0.
6. Når pakke n vælges, skal den resterende kapacitet reduceres med W[n-1].

Rettelse af bemærkning: den oprindelige kodestykke-muterede parameter M mens man stadig læser B[n][M]Den sikrere version ovenfor bruger en separat markør j for trace.

Java Driveren kører algoritmen på to bearbejdede 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);
}

Output for det første eksempel:

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

Output for det andet eksempel:

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 rumkompleksitet af 0/1 rygsæk

• Tidskompleksitet: O(n · M) — de to indbyggede løkker fejer n elementer hen over M+1 kapacitetstilstande.
• Rumkompleksitet: O(n · M) for hele tabellen, reducerbar til O(M) ved keeping kun den forrige række, når trace-back er ikke nødvendigt.

Køretiden er pseudo-polynomium: polynomium i værdien af ​​M, men eksponentielt i de bits, der bruges til at kode M. Derfor forbliver 0/1 Knapsack NP-hård, selvom dynamisk programmering er effektiv i praksis.

Anvendelser af 0/1 rygsækproblemet

• Lastning, containerpakning og plukning på lager under vægtgrænser.
• Budgetfordeling på tværs af investeringsprojekter med faste omkostninger og forventet afkast.
• Problemer med opskæring af lagerbeholdning i produktionen, der ikke kan opdele individuelle stykker.
• Kryptografiske ordninger som Merkle-Hellman, der bygger på rygsækhårdhed.
• Ressourcebegrænset planlægning i cloud computing og CPU-opgaveplacering.
• Funktionsudvælgelse i maskinlæring under et fast funktionsbudget.

Ofte Stillede Spørgsmål