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

Hvad er rygsækproblemet?

Rullesæk problem Algoritme er et meget nyttigt problem i kombinatorik. I supermarkedet er der n pakker (n ≤ 100) pakken i har vægt W[i] ≤ 100 og værdi V[i] ≤ 100. En tyv bryder ind i supermarkedet, tyven kan ikke bære vægt, der overstiger M (M ≤ 100) ). Problemet, der skal løses her, er: hvilke pakker vil tyven tage væk for at få den højeste 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:

Maksimer værdi og tilsvarende vægt i kapacitet.
Hvilke pakker vil tyven tage med.

Rugsækalgoritme kan yderligere opdeles i to typer:

0/1 Knapsack-problemet ved hjælp af dynamisk programmering. I denne Knapsack-algoritme kan hver pakke tages eller ikke tages. Desuden kan tyven ikke tage en brøkdel af en taget pakke eller tage en pakke mere end én gang. Denne type kan løses ved Dynamic Programming Approach.
Fractional Napsack problem algoritme. Denne type kan løses af Greedy Strategy.

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

I del-og-hersk-strategien opdeler du det problem, der skal løses, i delproblemer. Delproblemerne er yderligere opdelt i mindre delproblemer. Den opgave fortsætter, indtil du får delproblemer, der let kan løses. Men i processen med en sådan opdeling kan du støde på det samme problem mange gange.

Den grundlæggende idé med Knapsack dynamisk programmering er at bruge en tabel til at gemme løsninger af løste delproblemer. Står du over for et delproblem igen, skal du blot tage løsningen i tabellen uden at skulle løse det igen. Derfor er algoritmerne designet af dynamisk programmering meget effektive.

For at løse et problem ved dynamisk programmering skal du udføre følgende opgaver:

Find løsninger på de mindste delproblemer.
Find ud af formlen (eller reglen) for at bygge en løsning af delproblem gennem løsninger af selv de mindste delproblemer.
Lav en tabel, der gemmer løsningerne af delproblemer. Beregn derefter løsningen af delproblemet efter den fundne formel og gem i tabellen.
Ud fra de løste delopgaver finder du løsningen på det oprindelige problem.

Analyser 0/1 Rullesæk-problemet

Når du analyserer 0/1 Knapsack-problem ved hjælp af dynamisk programmering, kan du finde nogle bemærkelsesværdige punkter. Værdien af rygsækalgoritmen afhænger af to faktorer:

Hvor mange pakker overvejes
Den resterende vægt, som rygsækken kan opbevare.

Derfor har du to variable mængder.

Med dynamisk programmering har du nyttige oplysninger:

objektivfunktionen vil afhænge af to variable størrelser
tabellen over muligheder vil være en 2-dimensionel tabel.

Hvis kald B[i][j] er den maksimalt mulige værdi ved at vælge i pakker {1, 2, …, i} med vægtgrænse j.

Den maksimale værdi, når den vælges i n pakker med vægtgrænsen M, er B[n][M]. Med andre ord: Når der er i-pakker at vælge imellem, er B[i][j] den optimale vægt, når rygsækkens maksimale vægt er j.
Den optimale vægt er altid mindre end eller lig med den maksimale vægt: B[i][j] ≤ j.

For eksempel: B[4][10] = 8. Det betyder, at i det optimale tilfælde er den samlede vægt af de valgte pakker 8, når der er 4 første pakker at vælge imellem (1. til 4. pakke) og den maksimale vægt af rygsækken er 10. Det er ikke nødvendigt, at alle 4 varer er udvalgt.

Formel til at beregne B[i][j]

Input, du definerer:

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

I tilfælde af blot at have 1 pakke at vælge imellem. Du beregner B[1][j] for hver j: hvilket betyder rygsækkens maksimale vægt ≥ vægten af 1. pakke

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

Med vægtgrænsen j vil de optimale valg blandt pakkerne {1, 2, …, i – 1, i} for at have den største værdi have to muligheder:

Hvis pakke i ikke er valgt, er B[i][j] den maksimalt mulige værdi ved at vælge blandt pakker {1, 2, …, i – 1} med vægtgrænse på j. Du har:

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

Hvis pakke i er valgt (betragt naturligvis kun dette tilfælde, når W[i] ≤ j), så er B[i][j] lig med værdien V[i] af pakke i plus den maksimale værdi kan opnås ved at vælge blandt pakker {1, 2, …, i – 1} med vægtgrænse (j – W[i]). Det vil sige i forhold til den værdi, du har:

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

På grund af oprettelsen af B[i][j], som er den maksimalt mulige værdi, vil B[i][j] være maks. af ovenstående 2 værdier.

Grundlag for dynamisk programmering

Så du skal overveje, om det er bedre at vælge pakke i eller ej. Derfra har du den rekursive formel som følger:

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

Det er let at se B[0][j] = maksimal værdi ved at vælge fra 0 pakke = 0.

Beregn tabellen over muligheder

Du bygger en tabel med muligheder baseret på ovenstående rekursive formel. For at kontrollere, om resultaterne er korrekte (hvis ikke nøjagtigt, genopbygger du objektivfunktionen B[i][j]). Gennem oprettelsen af objektivfunktionen B[i][j] og tabellen med muligheder, vil du orientere sporingen.

Tabel over muligheder B inkluderer n + 1 linjer, M + 1 kolonner,

For det første udfyldt med grundlaget for dynamisk programmering: Linje 0 inkluderer alle nuller.
Brug rekursive formler, brug linje 0 til at beregne linje 1, brug linje 1 til at beregne linje 2 osv. … indtil alle linjer er beregnet.

Beregn tabellen over muligheder — Tabel over muligheder

Trace

Når du beregner tabellen over muligheder, er du interesseret i B[n][M], som er den maksimale værdi, der opnås ved at vælge i alle n pakker med vægtgrænsen M.

If B[n][M] = B[n – 1][M] så er pakke n ikke valgt, du sporer B[n – 1][M].
If B[n][M] ≠ B[n – 1][M], bemærker du, at det optimale valg har pakken n og spor B[n – 1][M – W[n]].

Fortsæt med at spore, indtil du når række 0 i tabellen med muligheder.

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

Bemærk: Hvis B[i][j] = B[i – 1][j], er pakken i ikke valgt. B[n][W] er den optimale samlede værdi af pakken lagt i rygsækken.

Trin til sporing:

Trin 1: Startende fra i = n, j = M.
Trin 2: Se i kolonne j, op fra bunden, finder du linjen i sådan, at B[i][j] > B[i – 1][j]. Marker valgt pakke i: Vælg [i] = sand;
Trin 3: j = B[i][j] – W[i]. Hvis j > 0, gå til trin 2, ellers gå til trin 4
Trin 4: Baseret på tabellen over muligheder for at udskrive de valgte pakker.

Java Kode

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

Forklaring af rygsækkode:

Opret tabel B[][]. Indstil standardværdi for hver celle er 0.
Byg tabel B[][] nedefra og op. Beregn tabellen over muligheder med genfindingsformlen.
Beregn B[i][j]. Hvis du ikke vælger pakke i.
Evaluer derefter: Hvis du vælger pakke i, vil det være mere fordelagtigt end at nulstille B[i][j].
Spor tabellen fra række n til række 0.
Hvis du vælger pakke n. Når du har valgt pakke n, kan du kun tilføje vægt M – W[n – 1].

I denne tutorial har du to eksempler. Her er java-kode til at køre ovenstående program med to eksempler:

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

Du har output:

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

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

Du kan lide: