0/1 Knapsack Problem Fix med hjälp av dynamiskt programmeringsexempel

Vad är knepsäcksproblemet?

Ocuco-landskapet Knapsäcksproblem är ett klassiskt kombinatoriskt optimeringsproblem. En stormarknadsbutik n paket (n ≤ 100). Paket i har vikt W[i] ≤ 100 och värde V[i] ≤ 100. En tjuv kan inte bära vikt som överstiger kapaciteten M (M ≤ 100). Vilka paket bör tjuven ta för att maximera det totala värdet?

Ingång:

• Maxvikt M och antalet förpackningar n.
• Array av vikt W[i] och motsvarande värde V[i].

Produktion:

• Maximalt totalvärde som kan erhållas inom kapaciteten.
• Den exakta uppsättning paket som tjuven ska ta.

Knapsack-algoritmen delas upp i två välkända varianter:

• 0/1 Ryggsäcksproblem löses med dynamisk programmering. Varje paket tas antingen helt eller lämnas kvar — inga bråkdelar och inga dubbletter.
• Problem med fraktionerad ryggsäck löst med en girig strategi. Här kan du ta en bråkdel av vilket paket som helst för att fylla den återstående kapaciteten.

Hur man löser Knapsack-problem med hjälp av dynamisk programmering med exempel

Söndra och härska delar upp ett stort problem i delproblem och fortsätter sedan att dela upp det tills varje delproblem är enkelt. Enkel rekursion löser dock ofta samma delproblem många gånger och slösar bort arbete.

Kärnidén med Knapsack Dynamic Programming är att lagra varje löst delproblem i en tabell. Upprepade anrop läser svaret istället för att beräkna det igen, vilket omvandlar en exponentiell rekursion till polynomialtidskod.

Lös Knapsack-problem med dynamisk programmering

För att designa en dynamisk programmeringslösning följer du fyra steg:

• Lös de minsta delproblemen först.
• Härled en repetition som bygger ett delproblemssvar från mindre repetitioner.
• Lagra svar på delproblem i en tabell beräknad bottom-up med hjälp av rekursionen.
• Sammanställ det slutliga svaret från den fullständigt ifyllda tabellen.

Analysera 0/1 Knapsack Problem

Det optimala värdet beror på två oberoende faktorer:

1. Hur många paket övervägs fortfarande?
2. Den återstående vikten kan ryggsäcken fortfarande lagra.

Eftersom målfunktionen är beroende av två kvantiteter måste tabellen med alternativ vara tvådimensionell. Låt B[i][j] betecknar det maximala värdet vid val mellan paket {1, …, i} med viktgräns j.

• Det slutgiltiga svaret är B[n][M], det bästa totalvärdet för alla n paket under kapacitet M.
• Den totala valda vikten begränsas alltid av den aktuella kapaciteten: B[i][j] ≤ j.

Exempel: om B[4][10] = 8, är den bästa totalvikten från de fyra första paketen under kapacitet 10 8. Några av dessa fyra paket kan hoppas över.

Formel för att beräkna B[i][j]

• W[i], V[i] är vikten och värdet av paket i, där i är i {1, …, n}.
• M är den maximala vikten ryggsäcken kan bära.

Basfall med ett paket: för varje kapacitet j ≥ W[1]:

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

För det allmänna fallet, avgör om paket i ska inkluderas under kapacitet j:

• Om paket i är hoppat över, B[i][j] är lika med det bästa värdet med paket {1, …, i-1} under kapacitet j:

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

• Om paket i är tagen (endast tillåtet när W[i] ≤ j), B[i][j] är lika med V[i] plus det bästa värdet från paketen {1, …, i-1} under kapacitet j – W[i]:

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

Ta den större av de två kandidaterna.

Grund för dynamisk programmering

Att kombinera de två fallen ger den fullständiga repetitionen:

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

Grundfallet är B[0][j] = 0 för varje j, eftersom nollpaket ger noll värde oavsett kapacitet.

Beräkna tabellen över alternativ

Bygg B med hjälp av repetitionen. När B är fyllt, driver samma tabell trace-back som rekonstruerar de valda paketen. Tabell B har n + 1 rader och M + 1 kolumner:

• Rad 0 är basfallet, fyllt med nollor.
• Använd rad 0 för att beräkna rad 1, rad 1 för att beräkna rad 2 och fortsätt tills rad n är komplett.

Tabell över alternativ

Trace

När B är klart, fokusera på B[n][M], det optimala totalvärdet över alla n paket med kapacitet M.

• If B[n][M] = B[n-1][M], paket n valdes inte, så fortsätt tracfrån B[n-1][M].
• If B[n][M] ≠ B[n-1][M], paket n valdes, så fortsätt tracfrån B[n-1][M – W[n]].

Upprepa tills du når rad 0 i tabellen.

Algoritm för att slå upp alternativtabellen för att hitta de valda paketen

Obs: närhelst B[i][j] = B[i-1][j], paket i är inte valt. Värdet B[n][M] är det optimala totalvärdet packat i ryggsäcken.

Steg för tracde valda paketen:

• Steg 1: Börja vid i = n, j = M.
• Steg 2: Skanna kolumn j nerifrån och upp tills du hittar rad i där B[i][j] > B[i-1][j]. Markera paket i som valt: Select[i] = true.
• Steg 3: Uppdatera j = j – W[i]. Om j > 0, gå tillbaka till steg 2, annars gå till steg 4.
• Steg 4: Skriv ut alla paket som markerats som valda.

Java Code

Följande Java Metoden fyller B[][] nerifrån och upp, skriver ut tabellen för inspektion och skriver sedan ut den. tracde valda paketen.

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() in Java

Förklaring av koden:

1. Allokera tabell B[][] och initiera varje cell till 0.
2. Fyll B[][] nerifrån och upp med hjälp av repetitionen från föregående avsnitt.
3. Börja varje cell med värdet "hoppa över paket i" B[i-1][j].
4. Om det är möjligt att välja paket i och ger ett strikt bättre värde, skriv över cellen.
5. TracFlytta de markerade objekten från rad n tillbaka till rad 0.
6. Närhelst paket n väljs, minska den återstående kapaciteten med W[n-1].

Åtgärdsanmärkning: den ursprungliga parametern för kodavsnittet muterade M medan man fortfarande läser B[n][M]Den säkrare versionen ovan använder en separat markör j för trace.

Ocuco-landskapet Java drivrutinen kör algoritmen på två utförda exempel:

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 för det första exemplet:

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 för det andra exemplet:

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- och rumskomplexitet hos 0/1 ryggsäck

• Tidskomplexitet: O(n · M) — de två kapslade looparna sveper n objekt över M+1 kapacitetstillstånd.
• Rymdkomplexitet: O(n · M) för hela tabellen, reducerbar till O(M) med keeping bara föregående rad när trace-back behövs inte.

Körtiden är pseudo-polynom: polynom i värdet av M men exponential i bitarna som används för att koda M. Det är därför 0/1 Knapsack förblir NP-svår även om dynamisk programmering är effektivt i praktiken.

Tillämpningar av 0/1 ryggsäcksproblemet

• Lastning, containerpackning och lagerplockning under viktgränser.
• Budgetfördelning över investeringsprojekt med fast kostnad och förväntad avkastning.
• Problem med skärande lager i tillverkningen som inte kan dela enskilda delar.
• Kryptografiska scheman som Merkle-Hellman som bygger på ryggsäckshårdhet.
• Resursbegränsad schemaläggning i molntjänster och placering av CPU-uppgifter.
• Funktionsurval inom maskininlärning under en fast funktionsbudget.

Vanliga frågor