0/1 Knapzakprobleem opgelost met behulp van dynamisch programmeervoorbeeld

Wat is het knapzakprobleem?

De Knapzak probleem is een klassiek combinatorisch optimalisatieprobleem. Een supermarkt n pakketten (n ≤ 100). Pakket i Een pakket heeft een gewicht W[i] ≤ 100 en een waarde V[i] ≤ 100. Een dief mag geen gewicht meenemen dat de capaciteit M (M ≤ 100) overschrijdt. Welke pakketten moet de dief meenemen om de totale waarde te maximaliseren?

Input:

• Maximaal gewicht M en het aantal pakketten n.
• Array van gewicht W[i] en corresponderende waarde V[i].

Output:

• Maximale totale waarde die binnen de capaciteit kan worden behaald.
• De exacte set pakketten die de dief moet meenemen.

Het knapsack-algoritme kent twee bekende varianten:

• 0/1 rugzakprobleem Opgelost door dynamische programmering. Elk pakket wordt ofwel in zijn geheel meegenomen of achtergelaten — geen gedeeltelijke stukken en geen duplicaten.
• Fractioneel knapzakprobleem Opgelost door een gulzige strategie. Hier mag je een deel van een pakket nemen om de resterende capaciteit te vullen.

Hoe u een knapzakprobleem kunt oplossen met behulp van dynamisch programmeren met voorbeeld

De verdeel-en-heersmethode splitst een groot probleem op in deelproblemen en blijft dit doen totdat elk deelprobleem eenvoudig is. Gewone recursie daarentegen lost vaak hetzelfde deelprobleem meerdere keren op en verspilt werk.

Het kernidee van Knapsack Dynamic Programming is om elk opgelost deelprobleem in een tabel op te slaan. Herhaalde aanroepen lezen het antwoord in plaats van het opnieuw te berekenen, waardoor een exponentiële recursie wordt omgezet in code met polynomiale looptijd.

Los het knapzakprobleem op met behulp van dynamisch programmeren

Om een ​​dynamische programmeeroplossing te ontwerpen, volg je vier stappen:

• Los eerst de kleinste deelproblemen op.
• Leid een recursievergelijking af die een antwoord voor een deelprobleem opbouwt uit antwoorden voor kleinere problemen.
• Sla de antwoorden van de deelproblemen op in een tabel die van onder naar boven wordt berekend met behulp van de recursieve formule.
• Stel het eindantwoord samen op basis van de volledig ingevulde tabel.

Analyseer het 0/1 knapzakprobleem

De optimale waarde hangt af van twee onafhankelijke factoren:

1. Hoeveel pakketten worden er nog overwogen?
2. Het resterende gewicht dat de rugzak nog kan dragen.

Omdat de doelfunctie afhankelijk is van twee grootheden, moet de optietabel tweedimensionaal zijn. Laat B[i][j] geeft de maximale waarde aan bij het kiezen uit pakketten {1, …, i} met gewichtslimiet j.

• Het definitieve antwoord is B[n][M], de beste totale waarde over alle n pakketten onder capaciteit M.
• Het totale geselecteerde gewicht wordt altijd begrensd door de huidige capaciteit: B[i][j] ≤ j.

Voorbeeld: als B[4][10] = 8, is het beste totale gewicht van de eerste vier pakketten onder capaciteit 10 gelijk aan 8. Sommige van die vier pakketten kunnen worden overgeslagen.

Formule om B[i][j] te berekenen

• W[i], V[i] zijn het gewicht en de waarde van pakket i, waarbij i zich bevindt in {1, …, n}.
• M Dit is het maximale gewicht dat de rugzak kan dragen.

Basisgeval met één pakket: voor elke capaciteit j ≥ W[1]:

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

Bepaal in het algemene geval of pakket i onder capaciteit j moet worden opgenomen:

• Als pakket i is overgeslagen, B[i][j] is gelijk aan de beste waarde met behulp van pakketten {1, …, i-1} onder capaciteit j:

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

• Als pakket i is ingenomen (alleen toegestaan ​​wanneer W[i] ≤ j), B[i][j] is gelijk aan V[i] plus de beste waarde uit pakketten {1, …, i-1} onder capaciteit j – W[i]:

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

Kies de grootste van de twee kandidaten.

Basis van dynamisch programmeren

Door de twee gevallen te combineren, verkrijgen we de volledige herhaling:

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

Het basisgeval is B[0][j] = 0 voor elke j, omdat nul pakketten een waarde van nul opleveren, ongeacht de capaciteit.

Bereken de tabel met opties

Bouw B op met behulp van de recursie. Zodra B gevuld is, stuurt dezelfde tabel de rest aan. trace-back die de gekozen pakketten reconstrueert. Tabel B heeft n + 1 rijen en M + 1 kolommen:

• Rij 0 is het basisgeval, gevuld met nullen.
• Gebruik rij 0 om rij 1 te berekenen, rij 1 om rij 2 te berekenen, en ga zo door tot rij n compleet is.

Tabel met opties

Trace

Zodra B is voltooid, concentreer je je op B[n][M], de optimale totale waarde over alle n pakketten met capaciteit M.

• If B[n][M] = B[n-1][M]Pakket n is niet geselecteerd, dus ga verder. tracing van B[n-1][M].
• If B[n][M] ≠ B[n-1][M]Pakket n is geselecteerd, dus ga verder. tracing van B[n-1][M – W[n]].

Herhaal dit totdat je bij rij 0 van de tabel bent aangekomen.

Algoritme om de tabel met opties op te zoeken om de geselecteerde pakketten te vinden

Opmerking: telkens B[i][j] = B[i-1][j]Pakket i is niet geselecteerd. De waarde B[n][M] is de optimale totale waarde die in de rugzak past.

Stappen voor tracde gekozen pakketten:

• Stap 1: Begin bij i = n, j = M.
• Stap 2: Scan kolom j van onder naar boven totdat je een rij i vindt waar B[i][j] > B[i-1][j]. Markeer pakket i als geselecteerd: Select[i] = true.
• Stap 3: Update j = j – W[i]. Als j > 0, ga terug naar stap 2, anders ga naar stap 4.
• Stap 4: Print elk pakket dat als geselecteerd is gemarkeerd.

Java Code

De volgende Java De methode vult B[][] van onder naar boven, print de tabel ter inspectie en vervolgens traces de geselecteerde pakketten.

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

Functie knapsackDyProg() in Java

Uitleg van de code:

1. Tabel toewijzen B[][] en initialiseer elke cel op 0.
2. Vul B[][] van onder naar boven in met behulp van de recursie uit de vorige sectie.
3. Begin elke cel met de waarde "skip package i". B[i-1][j].
4. Als het mogelijk is om pakket i te kiezen en dit een duidelijk betere waarde oplevert, overschrijf dan de cel.
5. Trace de geselecteerde items van rij n terug naar rij 0.
6. Wanneer pakket n wordt gekozen, verlaag dan de resterende capaciteit met W[n-1].

Correctie-opmerking: het oorspronkelijke fragment heeft de parameter gemuteerd M terwijl ik nog steeds aan het lezen ben B[n][M]De veiligere versie hierboven gebruikt een aparte cursor. j voor de trace.

De Java De driver voert het algoritme uit op twee uitgewerkte voorbeelden:

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

Uitvoer voor het eerste voorbeeld:

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

Uitvoer voor het tweede voorbeeld:

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

Tijd- en ruimtecomplexiteit van 0/1 rugzakken

• Tijdcomplexiteit: O(n · M) — de twee geneste lussen doorlopen n items over M+1 capaciteitsstaten.
• Ruimtecomplexiteit: O(n · M) voor de volledige tabel, te reduceren tot O(M) door keeping alleen de vorige rij wanneer tracEen e-back is niet nodig.

De looptijd is pseudo-polynoom: polynoom in de waarde van M, maar exponentieel in het aantal bits dat gebruikt wordt om M te coderen. Daarom blijft 0/1 Knapsack NP-moeilijk, ook al is dynamisch programmeren in de praktijk efficiënt.

Toepassingen van het 0/1 knapzakprobleem

• Het laden van vracht, het inpakken van containers en het verzamelen van goederen in het magazijn, binnen de vastgestelde gewichtslimieten.
• Budgettoewijzing aan investeringsprojecten met vaste kosten en verwachte opbrengst.
• Snijproblemen in de productie waarbij afzonderlijke stukken niet gesplitst kunnen worden.
• Cryptografieschema's zoals Merkle-Hellman bouwen voort op knapsack-hardness.
• Resourcebeperkte planning in cloudcomputing en CPU-taaktoewijzing.
• Functieselectie in machine learning met een vast functiebudget.

Veelgestelde vragen