0/1 Hátizsák probléma megoldása dinamikus programozási példa segítségével

Mi a hátizsák probléma?

Hátizsák probléma Az algoritmus nagyon hasznos probléma a kombinatorikában. A szupermarketben n csomag van (n ≤ 100), az i csomag súlya W[i] ≤ 100, értéke V[i] ≤ 100. A tolvaj behatol a szupermarketbe, a tolvaj nem tud M-nél nagyobb súlyt (M ≤ 100) szállítani. ). Itt a megoldandó probléma: mely csomagokat viszi el a tolvaj, hogy a legmagasabb értéket kapja?

Bemenet:

Maximális tömeg M és a csomagok száma n.
W[i] súlytömb és a megfelelő V[i] érték.

output:

Maximalizálja az értéket és a megfelelő súlyt a kapacitásban.
Melyik csomagokat viszi el a tolvaj.

A hátizsák algoritmus további két típusra osztható:

A 0/1 hátizsák probléma dinamikus programozással. Ebben a hátizsák-algoritmustípusban minden csomag felvehető vagy nem. Emellett a tolvaj nem vehet el egy elvitt csomag töredékét, és nem vehet el többször egy csomagot. Ezt a típust dinamikus programozási megközelítéssel lehet megoldani.
Tört hátizsák probléma algoritmus. Ezt a típust a Greedy Strategy megoldhatja.

Hátizsákprobléma megoldása dinamikus programozással példával

Az oszd meg és uralkodj stratégiában a megoldandó problémát részproblémákra osztod. A részproblémákat tovább osztjuk kisebb részproblémákra. Ez a feladat addig folytatódik, amíg könnyen megoldható részproblémákat nem kap. Az ilyen felosztás során azonban sokszor találkozhat ugyanazzal a problémával.

A hátizsákos dinamikus programozás alapötlete, hogy egy táblázat segítségével tároljuk a megoldott részproblémák megoldásait. Ha ismételten szembesül egy részproblémával, csak a táblázatban szereplő megoldást kell átvennie anélkül, hogy újra meg kellene oldania. Ezért a dinamikus programozás által megtervezett algoritmusok nagyon hatékonyak.

Egy probléma dinamikus programozással történő megoldásához a következő feladatokat kell végrehajtania:

Keressen megoldást a legkisebb részproblémákra.
Találja meg a képletet (vagy szabályt), amellyel a legkisebb részproblémák megoldásán keresztül is fel lehet építeni egy részprobléma megoldását.
Hozzon létre egy táblázatot, amely tárolja a részfeladatok megoldásait. Ezután számítsa ki a részfeladat megoldását a talált képlet alapján, és mentse el a táblázatba.
A megoldott részproblémák közül megtalálja az eredeti probléma megoldását.

Elemezze a 0/1 hátizsák problémát

A 0/1 hátizsák-probléma dinamikus programozással történő elemzésekor észrevehető pontokat találhat. A hátizsák-algoritmus értéke két tényezőtől függ:

Hány csomagot mérlegelnek
A hátralévő súly, amelyet a hátizsák tárolhat.

Ezért két változó mennyisége van.

A dinamikus programozással hasznos információkkal rendelkezik:

a célfüggvény két változó mennyiségtől fog függni
az opciók táblázata egy 2 dimenziós táblázat lesz.

Ha a B[i][j] hívása a maximális lehetséges érték, az {1, 2, …, i} csomagok kiválasztásával j súlykorlátozással.

A maximális érték, ha n csomagban van kiválasztva M súlykorlátozással, B[n][M]. Más szóval: Ha választható i csomagok, akkor B[i][j] az optimális súly, ha a hátizsák maximális súlya j.
Az optimális súly mindig kisebb vagy egyenlő, mint a maximális tömeg: B[i][j] ≤ j.

Például: B[4][10] = 8. Ez azt jelenti, hogy optimális esetben a kiválasztott csomagok össztömege 8, amikor 4 első csomag közül lehet választani (1-4 csomag) és a maximális súly A hátizsákból 10. Nem szükséges, hogy mind a 4 elem ki legyen jelölve.

Képlet a B[i][j] kiszámításához

Bemenet, Ön határozza meg:

W[i], V[i] viszont az i csomag súlya és értéke, amelyben i {1, …, n}.
M a maximális súly, amelyet a hátizsák elbír.

Abban az esetben, ha egyszerűen csak 1 csomag közül választhat. Minden j-re kiszámítja a B[1][j]-t: ami azt jelenti, hogy a hátizsák maximális súlya ≥ az 1. csomag súlya

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

A j súlykorlátozás mellett az {1, 2, …, i – 1, i} csomagok közötti optimális választásnak a legnagyobb értékhez két lehetősége van:

Ha az i csomag nincs kiválasztva, a B[i][j] a maximálisan lehetséges érték az {1, 2, …, i – 1} csomagok közül kiválasztva j súlykorlátozással. Neked van:

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

Ha az i csomagot választjuk (természetesen csak akkor vegyük ezt az esetet, ha W[i] ≤ j), akkor B[i][j] egyenlő az i csomag V[i] értékével, plusz a maximális érték a következők közül választható ki. csomagok {1, 2, …, i – 1} súlykorlátozással (j – W[i]). Vagyis az Ön értékét tekintve:

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

A maximális lehetséges érték B[i][j] létrehozása miatt B[i][j] lesz a fenti 2 érték maximuma.

A dinamikus programozás alapjai

Tehát mérlegelnie kell, hogy jobb-e az i csomagot választani vagy sem. Innentől kezdve megkapja a következő rekurzív képletet:

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

Könnyen belátható, hogy B[0][j] = a lehetséges maximális érték, ha 0 csomag = 0 közül választ.

Számítsa ki az opciók táblázatát

A fenti rekurzív képlet alapján összeállít egy opciótáblázatot. Annak ellenőrzésére, hogy az eredmények helyesek-e (ha nem pontosan, építse újra a B[i][j] célfüggvényt). A B[i][j] célfüggvény és az opciók táblázatának létrehozásával orientálja a nyomkövetést.

A B opciók táblázata n + 1 sort, M + 1 oszlopot tartalmaz,

Először is a dinamikus programozás alapjaival töltve: a 0. sor minden nullát tartalmaz.
Rekurzív képletekkel, használja a 0-s sort az 1. sor kiszámításához, használja az 1-es sort a 2. sor kiszámításához stb. … amíg az összes sort ki nem számítja.

Számítsa ki az opciók táblázatát — Lehetőségek táblázata

Nyom

Az opciók táblázatának kiszámításakor a B[n][M] érdekli, ami a maximális érték, amelyet az M súlykorlátozású n csomagban történő kiválasztásnál kapunk.

If B[n][M] = B[n – 1][M] akkor az n csomag nincs kiválasztva, nyomon követed a B[n – 1][M]-t.
If B[n][M] ≠ B[n – 1][M], észreveszi, hogy az optimális kiválasztás az n csomaggal és a B[n – 1][M – W[n]] nyomvonallal rendelkezik.

Folytassa a nyomkövetést, amíg el nem éri a lehetőségek táblázatának 0. sorát.

Algoritmus az opciók táblázatában a kiválasztott csomagok megkereséséhez

Megjegyzés: Ha B[i][j] = B[i – 1][j], az i csomag nincs kiválasztva. B[n][W] a hátizsákba helyezett csomag optimális összértéke.

A nyomkövetés lépései:

1 lépés: i = n-ből kiindulva, j = M.
2 lépés: Nézze meg a j oszlopban alulról felfelé, megtalálja az i sort úgy, hogy B[i][j] > B[i – 1][j]. Jelölje ki a kiválasztott csomagot i: Válassza az [i] = igaz;
3 lépés: j = B[i][j] – W[i]. Ha j > 0, folytassa a 2. lépéssel, ellenkező esetben folytassa a 4. lépéssel
4 lépés: A kiválasztott csomagok nyomtatására vonatkozó lehetőségek táblázata alapján.

Java Kód

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

A hátizsák kód magyarázata:

B[][] tábla létrehozása. Az egyes cellák alapértelmezett értéke 0.
Építsd fel a B[][] táblázatot alulról felfelé haladva. Számítsa ki a lehetőségek táblázatát a visszakeresési képlettel!
B[i][j] kiszámítása. Ha nem választja ki az i.
Ezután értékelje: ha az i csomagot választja, az előnyösebb lesz, mint a B[i][j] visszaállítása.
Kövesse nyomon a táblázatot az n sortól a 0 sorig.
Ha az n. csomagot választja. Az n csomag kiválasztása után csak M – W[n – 1] súlyt adhat hozzá.

Ebben az oktatóanyagban két példa van. Íme a java kód a fenti program futtatásához, két példával:

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

Megvan a kimenet:

Első példa:

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

Második példa:

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