0/1 Problemă la rucsac Remediere folosind un exemplu de programare dinamică

Care este problema rucsacului?

Problemă la rucsac algoritmul este o problemă foarte utilă în combinatorică. În supermarket sunt n pachete (n ≤ 100) pachetul i are greutatea W[i] ≤ 100 și valoarea V[i] ≤ 100. Un hoț intră în supermarket, hoțul nu poate transporta o greutate mai mare de M (M ≤ 100). ). Problema care trebuie rezolvată aici este: ce pachete le va lua hoțul pentru a obține cea mai mare valoare?

Intrare:

Greutatea maximă M și numărul de pachete n.
Matrice de greutate W[i] și valoarea corespunzătoare V[i].

ieșire:

Maximizați valoarea și greutatea corespunzătoare în capacitate.
Ce pachete le va lua hoțul.

Algoritmul rucsac poate fi împărțit în două tipuri:

Problema rucsacului 0/1 folosind programarea dinamică. În acest tip de algoritm Knapsack, fiecare pachet poate fi luat sau nu. În plus, hoțul nu poate lua o cantitate fracțională dintr-un pachet luat sau să ia un pachet de mai multe ori. Acest tip poate fi rezolvat prin abordarea de programare dinamică.
Algoritmul problemei rucsac fracționat. Acest tip poate fi rezolvat de Greedy Strategy.

Cum se rezolvă problema rucsacului folosind programarea dinamică cu exemplu

În strategia împărțiți și cuceriți, împărțiți problema de rezolvat în subprobleme. Subproblemele sunt împărțite în continuare în subprobleme mai mici. Această sarcină va continua până când veți obține subprobleme care pot fi rezolvate cu ușurință. Cu toate acestea, în procesul unei astfel de împărțiri, este posibil să întâmpinați aceeași problemă de multe ori.

Ideea de bază a programării dinamice Knapsack este de a folosi un tabel pentru a stoca soluțiile subproblemelor rezolvate. Dacă vă confruntați din nou cu o subproblemă, trebuie doar să luați soluția din tabel fără a fi nevoie să o rezolvați din nou. Prin urmare, algoritmii proiectați prin programare dinamică sunt foarte eficienți.

Pentru a rezolva o problemă prin programare dinamică, trebuie să faceți următoarele sarcini:

Găsiți soluții pentru cele mai mici subprobleme.
Aflați formula (sau regula) pentru a construi o soluție a unei subprobleme prin soluții chiar și ale celor mai mici subprobleme.
Creați un tabel care stochează soluțiile subproblemelor. Apoi calculați soluția subproblemei conform formulei găsite și salvați în tabel.
Din subproblemele rezolvate, găsiți soluția problemei inițiale.

Analizați problema rucsacului 0/1

Când analizați problema 0/1 Rucsac folosind programarea dinamică, puteți găsi câteva puncte vizibile. Valoarea algoritmului de rucsac depinde de doi factori:

Câte pachete sunt luate în considerare
Greutatea rămasă pe care o poate stoca rucsacul.

Prin urmare, aveți două cantități variabile.

Cu programarea dinamică, aveți informații utile:

funcţia obiectiv va depinde de două mărimi variabile
tabelul de opțiuni va fi un tabel bidimensional.

Dacă apelarea B[i][j] este valoarea maximă posibilă selectând în pachetele {1, 2, …, i} cu limita de greutate j.

Valoarea maximă atunci când este selectată în n pachete cu limita de greutate M este B[n][M]. Cu alte cuvinte: Când există i pachete de ales, B[i][j] este greutatea optimă atunci când greutatea maximă a rucsacului este j.
Greutatea optimă este întotdeauna mai mică sau egală cu greutatea maximă: B[i][j] ≤ j.

De exemplu: B[4][10] = 8. Înseamnă că în cazul optim, greutatea totală a pachetelor selectate este de 8, când există 4 primele pachete din care să alegi (de la 1 la 4 pachet) și greutatea maximă. din rucsac este 10. Nu este necesar ca toate cele 4 articole să fie selectate.

Formula pentru a calcula B[i][j]

Intrare, definiți:

W[i], V[i] sunt la rândul lor greutatea și valoarea pachetului i, în care i {1, …, n}.
M este greutatea maximă pe care o poate suporta rucsacul.

În cazul pur și simplu a avea doar 1 pachet de ales. Calculați B[1][j] pentru fiecare j: ceea ce înseamnă greutatea maximă a rucsacului ≥ greutatea primului pachet

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

Cu limita de greutate j, selecțiile optime dintre pachetele {1, 2, …, i – 1, i} pentru a avea cea mai mare valoare vor avea două posibilități:

Dacă pachetul i nu este selectat, B[i][j] este valoarea maximă posibilă prin selectarea dintre pachetele {1, 2, …, i – 1} cu limita de greutate de j. Aveți:

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

Dacă este selectat pachetul i (desigur, luați în considerare doar acest caz când W[i] ≤ j), atunci B[i][j] este egal cu valoarea V[i] a pachetului i plus valoarea maximă poate fi obținută prin selectarea dintre pachete {1, 2, …, i – 1} cu limită de greutate (j – W[i]). Adică în ceea ce privește valoarea pe care o ai:

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

Datorită creării lui B[i][j], care este valoarea maximă posibilă, B[i][j] va fi maximul celor 2 valori de mai sus.

Baza programării dinamice

Deci, trebuie să vă gândiți dacă este mai bine să alegeți pachetul i sau nu. De acolo aveți formula recursivă după cum urmează:

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

Este ușor de văzut B[0][j] = valoarea maximă posibilă selectând din 0 pachet = 0.

Calculați tabelul de opțiuni

Construiți un tabel de opțiuni pe baza formulei recursive de mai sus. Pentru a verifica dacă rezultatele sunt corecte (dacă nu exact, reconstruiți funcția obiectiv B[i][j]). Prin crearea funcției obiectiv B[i][j] și a tabelului de opțiuni, veți orienta trasarea.

Tabelul de opțiuni B include n + 1 linii, M + 1 coloane,

În primul rând, umplut cu baza programării dinamice: linia 0 include toate zerourile.
Folosind formule recursive, utilizați linia 0 pentru a calcula linia 1, folosiți linia 1 pentru a calcula linia 2 etc. ... până când toate liniile sunt calculate.

Calculați tabelul de opțiuni — Tabel de Opțiuni

Urmă

La calcularea tabelului de opțiuni, vă interesează B[n][M] care este valoarea maximă obținută la selectarea în toate cele n pachete cu limita de greutate M.

If B[n][M] = B[n – 1][M] atunci pachetul n nu este selectat, urmăriți B[n – 1][M].
If B[n][M] ≠ B[n – 1][M], observați că selecția optimă are pachetul n și urma B[n – 1][M – W[n]].

Continuați să urmăriți până ajungeți la rândul 0 al tabelului de opțiuni.

Algoritm pentru a căuta tabelul de opțiuni pentru a găsi pachetele selectate

Notă: Dacă B[i][j] = B[i – 1][j], pachetul i nu este selectat. B[n][W] este valoarea totală optimă a pachetului pus în rucsac.

Pași pentru urmărire:

Etapa 1: Pornind de la i = n, j = M.
Etapa 2: Privește în coloana j, de jos în sus, găsești linia i astfel încât B[i][j] > B[i – 1][j]. Marcați pachetul selectat i: Selectați [i] = adevărat;
Etapa 3: j = B[i][j] – W[i]. Dacă j > 0, mergeți la pasul 2, în caz contrar treceți la pasul 4
Etapa 4: Pe baza tabelului de opțiuni de tipărire a pachetelor selectate.

Java Cod

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

Explicația codului rucsacului:

Creați tabelul B[][]. Valoarea implicită setată pentru fiecare celulă este 0.
Construiți tabelul B[][] de jos în sus. Calculați tabelul de opțiuni cu formula de recuperare.
Calculați B[i][j]. Dacă nu selectați pachetul i.
Apoi evaluați: dacă selectați pachetul i, va fi mai benefic decât resetați B[i][j].
Urmăriți tabelul de la rândul n până la rândul 0.
Daca alegi pachetul n. Odată selectat pachetul n, se poate adăuga doar greutatea M – W[n – 1].

În acest tutorial, aveți două exemple. Iată codul java pentru a rula programul de mai sus cu două exemple:

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

Aveți rezultatul:

Primul exemplu:

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

Al doilea exemplu:

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