0/1 Knapzakprobleem opgelost met behulp van dynamisch programmeervoorbeeld

Wat is het knapzakprobleem?

Knapzak probleem algoritme is een zeer nuttig probleem in de combinatoriek. In de supermarkt zijn er n pakjes (n ≤ 100) het pakje i heeft gewicht W[i] ≤ 100 en waarde V[i] ≤ 100. Een dief breekt in in de supermarkt, de dief kan geen gewicht dragen dat groter is dan M (M ≤ 100 ). Het probleem dat hier moet worden opgelost is: welke pakketten zal de dief meenemen om de hoogste waarde te krijgen?

Input:

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

Output:

Maximaliseer de waarde en het bijbehorende gewicht in capaciteit.
Welke pakketten de dief meeneemt.

Knapzakalgoritme kan verder worden onderverdeeld in twee typen:

Het 0/1 Knapzakprobleem met behulp van dynamisch programmeren. Bij dit type Knapzak-algoritme kan elk pakket wel of niet worden meegenomen. Bovendien mag de dief geen fractie van een meegenomen pakket meenemen, noch een pakket meer dan één keer meenemen. Dit type kan worden opgelost met een dynamische programmeerbenadering.
Algoritme voor fractioneel knapzakprobleem. Dit type kan worden opgelost door Greedy Strategy.

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

Bij de verdeel-en-heersstrategie verdeel je het op te lossen probleem in deelproblemen. De deelproblemen zijn verder onderverdeeld in kleinere deelproblemen. Die taak gaat door totdat je deelproblemen krijgt die gemakkelijk kunnen worden opgelost. Tijdens het proces van een dergelijke verdeling kunt u echter vaak hetzelfde probleem tegenkomen.

Het basisidee van Knapsack dynamische programmering is om een tabel te gebruiken om de oplossingen van opgeloste subproblemen op te slaan. Als je opnieuw met een subprobleem te maken krijgt, hoef je alleen maar de oplossing in de tabel te nemen zonder het opnieuw op te hoeven lossen. Daarom zijn de algoritmen die door dynamische programmering zijn ontworpen, zeer effectief.

Om een probleem op te lossen met behulp van dynamische programmering, moet u de volgende taken uitvoeren:

Vind oplossingen voor de kleinste deelproblemen.
Ontdek de formule (of regel) om een oplossing voor een deelprobleem te bouwen door middel van oplossingen voor zelfs de kleinste deelproblemen.
Maak een tabel waarin de oplossingen van deelproblemen worden opgeslagen. Bereken vervolgens de oplossing van het deelprobleem volgens de gevonden formule en sla deze op in de tabel.
Uit de opgeloste deelproblemen vind je de oplossing van het oorspronkelijke probleem.

Analyseer het 0/1 knapzakprobleem

Wanneer u het 0/1 Knapzakprobleem analyseert met behulp van dynamisch programmeren, kunt u enkele opvallende punten ontdekken. De waarde van het knapzakalgoritme hangt af van twee factoren:

Hoeveel pakketten worden overwogen
Het resterende gewicht dat de knapzak kan dragen.

Je hebt dus twee variabele hoeveelheden.

Met dynamisch programmeren beschikt u over nuttige informatie:

de objectieve functie zal afhangen van twee variabele grootheden
de tabel met opties zal een tweedimensionale tabel zijn.

Als het aanroepen van B[i][j] de maximaal mogelijke waarde is door in pakketten {1, 2, …, i} met gewichtslimiet j te selecteren.

De maximale waarde bij selectie in n pakketten met de gewichtslimiet M is B[n][M]. Met andere woorden: als er i pakketten zijn om uit te kiezen, is B[i][j] het optimale gewicht als het maximale gewicht van de knapzak j is.
Het optimale gewicht is altijd kleiner dan of gelijk aan het maximale gewicht: B[i][j] ≤ j.

Bijvoorbeeld: B[4][10] = 8. Dit betekent dat in het optimale geval het totale gewicht van de geselecteerde pakketten 8 is, wanneer er 4 eerste pakketten zijn om uit te kiezen (1e tot en met 4e pakket) en het maximale gewicht van de knapzak is 10. Het is niet nodig dat alle 4 de items zijn geselecteerd.

Formule om B[i][j] te berekenen

Invoer, u definieert:

W[i], V[i] zijn op hun beurt het gewicht en de waarde van pakket i, waarin i {1, …, n}.
M is het maximale gewicht dat de knapzak kan dragen.

In het geval dat u eenvoudigweg maar uit 1 pakket kunt kiezen. Voor elke j bereken je B[1][j]: dat wil zeggen het maximale gewicht van de knapzak ≥ het gewicht van het 1e pakket

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

Met de gewichtslimiet j hebben de optimale selecties tussen pakketten {1, 2, …, i – 1, i} om de grootste waarde te hebben twee mogelijkheden:

Als pakket i niet is geselecteerd, is B[i][j] de maximaal mogelijke waarde door te kiezen uit pakketten {1, 2, …, i – 1} met een gewichtslimiet van j. Je hebt:

B[i][j] = B[i – 1][j]

Als pakket i wordt geselecteerd (beschouw dit geval uiteraard alleen als W[i] ≤ j), dan is B[i][j] gelijk aan de waarde V[i] van pakket i plus de maximale waarde die kan worden verkregen door te selecteren uit pakketten {1, 2, …, i – 1} met gewichtslimiet (j – W[i]). Dat wil zeggen, in termen van de waarde die u heeft:

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

Vanwege de creatie van B[i][j], wat de maximaal mogelijke waarde is, zal B[i][j] de max zijn van de bovenstaande 2 waarden.

Basis van dynamisch programmeren

U moet dus overwegen of het beter is om pakket i te kiezen of niet. Van daaruit heb je de recursieve formule als volgt:

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

Het is gemakkelijk om B[0][j] = de maximale waarde te zien die mogelijk is door te kiezen uit 0 pakket = 0.

Bereken de tabel met opties

U bouwt een tabel met opties op basis van de bovenstaande recursieve formule. Om te controleren of de resultaten correct zijn (zo niet precies, herbouwt u de doelfunctie B[i][j]). Door het creëren van de doelfunctie B[i][j] en de tabel met opties, kunt u de tracering oriënteren.

Tabel met opties B omvat n + 1 regels, M + 1 kolommen,

Ten eerste gevuld met de basis van dynamisch programmeren: regel 0 bevat allemaal nullen.
Gebruik recursieve formules: gebruik regel 0 om regel 1 te berekenen, gebruik regel 1 om regel 2 te berekenen, enz. … totdat alle regels zijn berekend.

Bereken de tabel met opties — Tabel met opties

Opsporen

Bij het berekenen van de optiestabel bent u geïnteresseerd in B[n][M], wat de maximale waarde is die wordt verkregen bij het selecteren van alle n pakketten met de gewichtslimiet M.

If B[n][M] = B[n – 1][M] dan is pakket n niet geselecteerd, je traceert B[n – 1][M].
If B[n][M] ≠ B[n – 1][M], merk je dat de optimale selectie het pakket n en trace B[n – 1][M – W[n]] heeft.

Blijf traceren totdat u rij 0 van de tabel met opties bereikt.

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

Opmerking: Als B[i][j] = B[i – 1][j], wordt pakket i niet geselecteerd. B[n][W] is de optimale totale waarde van het pakket dat in de knapzak wordt gestopt.

Stappen voor tracering:

Stap 1: Beginnend met i = n, j = M.
Stap 2: Kijk in kolom j, van boven naar beneden, je vindt de lijn i zo dat B[i][j] > B[i – 1][j]. Geselecteerd pakket i markeren: Selecteer [i] = true;
Stap 3: j = B[i][j] – W[i]. Als j > 0, ga naar stap 2, anders ga naar stap 4
Stap 4: Gebaseerd op de tabel met opties om de geselecteerde pakketten af te drukken.

Java Code

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: ");
	
	while (n != 0) {
		if (B[n][M] != B[n - 1][M]) {
			System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
			
			M = M - W[n-1];
		}
		
		n--;
	}
}

Uitleg Knapzakcode:

Maak tabel B[][]. De standaardwaarde voor elke cel is 0.
Bouw tabel B[][] bottom-up op. Bereken de tabel met opties met de ophaalformule.
Bereken B[i][j]. Als u pakket i.
Evalueer vervolgens: als u pakket i selecteert, is dit voordeliger dan het opnieuw instellen van B[i][j].
Volg de tabel van rij n naar rij 0.
Als u kiest voor pakket n. Nadat u pakket n heeft geselecteerd, kunt u alleen gewicht M – W[n – 1] toevoegen.

In deze zelfstudie vindt u twee voorbeelden. Hier is Java-code om het bovenstaande programma uit te voeren met twee voorbeelden:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	//int W[] = new int[]{3, 4, 5, 9, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
	//int V[] = new int[]{3, 4, 4, 10, 4};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
	//int M = 11;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackDyProg(W, V, M, n);
}

Je hebt de uitvoer:

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

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