0/1 Knapsekkproblemfiks ved hjelp av dynamisk programmeringseksempel

Hva er ryggsekkproblemet?

Rullesekk problem Algoritme er et svært nyttig problem i kombinatorikk. I supermarkedet er det n pakker (n ≤ 100) pakken i har vekt W[i] ≤ 100 og verdi V[i] ≤ 100. En tyv bryter seg inn i supermarkedet, tyven kan ikke bære vekt som overstiger M (M ≤ 100 ). Problemet som skal løses her er: hvilke pakker vil tyven ta for å få høyest verdi?

Inngang:

• Maksimal vekt M og antall pakker n.
• Array av vekt W[i] og tilsvarende verdi V[i].

Utgang:

• Maksimer verdi og tilsvarende vekt i kapasitet.
• Hvilke pakker vil tyven ta med seg.

Ryggsekkalgoritmen kan videre deles inn i to typer:

• 0/1 Knapsack-problemet ved bruk av dynamisk programmering. I denne typen napsekkalgoritme kan hver pakke tas eller ikke tas. Dessuten kan ikke tyven ta en brøkdel av en tatt pakke eller ta en pakke mer enn én gang. Denne typen kan løses ved Dynamic Programming Approach.
• Fractional Napsack problem algoritme. Denne typen kan løses av Greedy Strategy.

Hvordan løse Knapsack-problem ved hjelp av dynamisk programmering med eksempel

I del-og-hersk-strategien deler du opp problemet som skal løses i delproblemer. Delproblemene er videre delt inn i mindre delproblemer. Den oppgaven vil fortsette til du får delproblemer som enkelt kan løses. I prosessen med en slik deling kan du imidlertid støte på det samme problemet mange ganger.

Den grunnleggende ideen med Knapsack dynamisk programmering er å bruke en tabell for å lagre løsningene av løste delproblemer. Står du overfor et delproblem igjen, trenger du bare å ta løsningen i tabellen uten å måtte løse det på nytt. Derfor er algoritmene designet av dynamisk programmering svært effektive.

For å løse et problem ved dynamisk programmering, må du gjøre følgende oppgaver:

• Finn løsninger på de minste delproblemene.
• Finn ut formelen (eller regelen) for å bygge en løsning av delproblem gjennom løsninger av selv de minste delproblemer.
• Lag en tabell som lagrer løsningene til delproblemer. Regn deretter ut løsningen av delproblemet i henhold til den funnet formelen og lagre i tabellen.
• Fra de løste deloppgavene finner du løsningen på det opprinnelige problemet.

Analyser 0/1 ryggsekkproblemet

Når du analyserer 0/1 Knapsack-problem ved hjelp av dynamisk programmering, kan du finne noen merkbare punkter. Verdien av ryggsekkalgoritmen avhenger av to faktorer:

1. Hvor mange pakker vurderes
2. Den gjenværende vekten som ryggsekken kan lagre.

Derfor har du to variable mengder.

Med dynamisk programmering har du nyttig informasjon:

1. objektivfunksjonen vil avhenge av to variable størrelser
2. tabellen over alternativer vil være en 2-dimensjonal tabell.

Hvis å ringe B[i][j] er den maksimalt mulige verdien ved å velge i pakkene {1, 2, …, i} med vektgrense j.

• Den maksimale verdien når valgt i n pakker med vektgrensen M er B[n][M]. Med andre ord: Når det er i-pakker å velge, er B[i][j] den optimale vekten når ryggsekkens maksimale vekt er j.
• Den optimale vekten er alltid mindre enn eller lik maksimalvekten: B[i][j] ≤ j.

For eksempel: B[4][10] = 8. Det betyr at i det optimale tilfellet er totalvekten på de valgte pakkene 8, når det er 4 første pakker å velge mellom (1. til 4. pakke) og maksimal vekt av ryggsekken er 10. Det er ikke nødvendig at alle 4 varene velges.

Formel for å beregne B[i][j]

Inndata, du definerer:

• W[i], V[i] er igjen vekten og verdien av pakke i, der i {1, …, n}.
• M er den maksimale vekten ryggsekken kan bære.

I tilfelle du bare har 1 pakke å velge. Du beregner B[1][j] for hver j: som betyr at ryggsekkens maksimale vekt ≥ vekten av den første pakken

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

Med vektgrensen j vil de optimale valgene blant pakkene {1, 2, …, i – 1, i} for å ha den største verdien ha to muligheter:

• Hvis pakke i ikke er valgt, er B[i][j] den maksimalt mulige verdien ved å velge blant pakkene {1, 2, …, i – 1} med vektgrense på j. Du har:

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

• Hvis pakke i er valgt (selvfølgelig vurdere kun dette tilfellet når W[i] ≤ j) så er B[i][j] lik verdien V[i] til pakke i pluss den maksimale verdien kan oppnås ved å velge blant pakker {1, 2, …, i – 1} med vektgrense (j – W[i]). Det vil si når det gjelder verdien du har:

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

På grunn av opprettelsen av B[i][j], som er den maksimalt mulige verdien, vil B[i][j] være maks av de 2 verdiene ovenfor.

Grunnlag for dynamisk programmering

Så du må vurdere om det er bedre å velge pakke i eller ikke. Derfra har du den rekursive formelen som følger:

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

Det er lett å se B[0][j] = maksimal verdi ved å velge fra 0 pakke = 0.

Beregn alternativtabellen

Du bygger en tabell med alternativer basert på den rekursive formelen ovenfor. For å sjekke om resultatene er korrekte (hvis ikke nøyaktig, bygger du om objektivfunksjonen B[i][j]). Gjennom opprettelsen av objektivfunksjonen B[i][j] og tabellen med alternativer, vil du orientere sporingen.

Tabell over alternativer B inkluderer n + 1 linjer, M + 1 kolonner,

• For det første fylt med grunnlaget for dynamisk programmering: Linje 0 inkluderer alle nuller.
• Bruk rekursive formler, bruk linje 0 til å beregne linje 1, bruk linje 1 til å beregne linje 2, osv. … til alle linjene er beregnet.

Trace

Når du beregner tabellen med alternativer, er du interessert i B[n][M] som er den maksimale verdien som oppnås når du velger i alle n pakker med vektgrensen M.

• If B[n][M] = B[n – 1][M] da er ikke pakke n valgt, du sporer B[n – 1][M].
• If B[n][M] ≠ B[n – 1][M], merker du at det optimale utvalget har pakken n og spor B[n – 1][M – W[n]].

Fortsett å spore til du når rad 0 i tabellen med alternativer.

Algoritme for å slå opp alternativtabellen for å finne de valgte pakkene

Merk: Hvis B[i][j] = B[i – 1][j], er ikke pakken i valgt. B[n][W] er den optimale totale verdien av pakken lagt i ryggsekken.

Trinn for sporing:

• Trinn 1: Starter fra i = n, j = M.
• Trinn 2: Se i kolonne j, opp fra bunnen, finner du linjen i slik at B[i][j] > B[i – 1][j]. Merk valgt pakke i: Velg [i] = sant;
• Trinn 3: j = B[i][j] – W[i]. Hvis j > 0, gå til trinn 2, ellers gå til trinn 4
• Trinn 4: Basert på tabellen med alternativer for å skrive ut de valgte pakkene.

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 av ryggsekkkode:

1. Lag tabell B[][]. Angi standardverdi for hver celle er 0.
2. Bygg tabell B[][] nedenfra og opp. Beregn tabellen med alternativer med gjenfinningsformelen.
3. Regn ut B[i][j]. Hvis du ikke velger pakke i.
4. Evaluer deretter: hvis du velger pakke i, vil det være mer fordelaktig enn å tilbakestille B[i][j].
5. Spor tabellen fra rad n til rad 0.
6. Hvis du velger pakke n. Når du har valgt pakke n, kan du bare legge til vekt M – W[n – 1].

I denne opplæringen har du to eksempler. Her er java-kode for å kjøre programmet ovenfor 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 utgangen:

• 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

• Andre 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