0/1 Oprava problému s batohem pomocí příkladu dynamického programování

Od: Sarah Chen Sarah Chen
Hours aktualizováno

Co je problém batohu?

Problém s batohem Algoritmus je velmi užitečný problém v kombinatorice. V supermarketu je n balíků (n ≤ 100) balík i má hmotnost W[i] ≤ 100 a hodnotu V[i] ≤ 100. Zloděj se vloupe do supermarketu, zloděj neunese váhu větší než M (M ≤ 100 ). Zde je třeba vyřešit problém: které balíčky si zloděj odnese, aby získal nejvyšší hodnotu?

Vstup:

  • Maximální hmotnost M a počet balíků n.
  • Pole hmotnosti W[i] a odpovídající hodnoty V[i].

Výstup:

  • Maximalizujte hodnotu a odpovídající hmotnost v kapacitě.
  • Které balíčky si zloděj odnese.

Algoritmus batohu lze dále rozdělit na dva typy:

  • Problém batohu 0/1 pomocí dynamického programování. V tomto typu algoritmu batohu může být každý balíček přijat nebo ne. Kromě toho si zloděj nemůže vzít zlomkové množství odebraného balíku nebo vzít balík více než jednou. Tento typ lze vyřešit přístupem dynamického programování.
  • Algoritmus problému frakčního batohu. Tento typ lze vyřešit pomocí Greedy Strategy.

Jak vyřešit problém s batohem pomocí dynamického programování s příkladem

Ve strategii rozděl a panuj rozdělíte problém, který se má vyřešit, na dílčí problémy. Dílčí problémy se dále dělí na menší dílčí problémy. Tento úkol bude pokračovat, dokud nezískáte dílčí problémy, které lze snadno vyřešit. V procesu takového dělení však můžete na stejný problém narazit mnohokrát.

Základní myšlenkou dynamického programování Knapsack je použití tabulky k ukládání řešení řešených dílčích problémů. Pokud znovu narazíte na dílčí problém, stačí vzít řešení v tabulce, aniž byste jej museli znovu řešit. Proto jsou algoritmy navržené dynamickým programováním velmi efektivní.

Vyřešte problém s batohem pomocí dynamického programování

Chcete-li vyřešit problém dynamickým programováním, musíte provést následující úkoly:

  • Najděte řešení nejmenších dílčích problémů.
  • Zjistěte vzorec (nebo pravidlo), abyste vytvořili řešení dílčího problému prostřednictvím řešení i těch nejmenších dílčích problémů.
  • Vytvořte tabulku, která ukládá řešení dílčích problémů. Poté vypočítejte řešení podúlohy podle nalezeného vzorce a uložte do tabulky.
  • Z vyřešených dílčích problémů najdete řešení původního problému.

Analyzujte problém batohu 0/1

Při analýze problému batohu 0/1 pomocí dynamického programování můžete najít některé pozoruhodné body. Hodnota algoritmu batohu závisí na dvou faktorech:

  1. Kolik balíčků se zvažuje
  2. Zbývající hmotnost, kterou může batoh uložit.

Máte tedy dvě proměnné veličiny.

S dynamickým programováním máte užitečné informace:

  1. účelová funkce bude záviset na dvou proměnných veličinách
  2. tabulka možností bude 2-rozměrná tabulka.

Pokud je volání B[i][j] maximální možnou hodnotou výběrem v balíčcích {1, 2, …, i} s hmotnostním limitem j.

  • Maximální hodnota při výběru v n obalech s hmotnostním limitem M je B[n][M]. Jinými slovy: Když je na výběr i balíčků, B[i][j] je optimální hmotnost, když je maximální hmotnost batohu j.
  • Optimální hmotnost je vždy menší nebo rovna maximální hmotnosti: B[i][j] ≤j.

Například: B[4][10] = 8. Znamená to, že v optimálním případě je celková hmotnost vybraných balíků 8, kdy jsou na výběr 4 první balíky (1. až 4. balík) a maximální hmotnost batohu je 10. Není nutné, aby byly vybrány všechny 4 položky.

SOUVISEJÍCÍ ČLÁNKY

Vzorec pro výpočet B[i][j]

Vstup, definujete:

  • W[i], V[i] jsou zase hmotnost a hodnota balení i, ve kterém i Vzorec pro výpočet B[i][j]{1, …, n}.
  • M je maximální hmotnost, kterou batoh unese.

V případě, že máte na výběr pouze 1 balení. Vypočítáte B[1][j] pro každé j: což znamená maximální hmotnost batohu ≥ hmotnost 1. balíku

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

S váhovým limitem j budou mít optimální výběr mezi balíčky {1, 2, …, i – 1, i}, aby měly největší hodnotu, dvě možnosti:

  • Pokud není vybráno balení i, B[i][j] je maximální možná hodnota výběrem mezi balíky {1, 2, …, i – 1} s hmotnostním limitem j. Ty máš:
B[i][j] = B[i – 1][j]
  • Pokud je vybrán balíček i (samozřejmě uvažujte pouze tento případ, kdy W[i] ≤ j), pak B[i][j] se rovná hodnotě V[i] balíčku i plus maximální hodnotu lze získat výběrem mezi balíky {1, 2, …, i – 1} s hmotnostním limitem (j – W[i]). To znamená, pokud jde o hodnotu, kterou máte:
B[i][j] = V[i] + B[i – 1][j – W[i]]

Vzhledem k vytvoření B[i][j], což je maximální možná hodnota, bude B[i][j] max z výše uvedených 2 hodnot.

Základy dynamického programování

Musíte tedy zvážit, zda je lepší zvolit balíček i nebo ne. Odtud máte rekurzivní vzorec takto:

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

Je snadné vidět B[0][j] = maximální možná hodnota výběrem z 0 balíček = 0.

Vypočítejte tabulku možností

Na základě výše uvedeného rekurzivního vzorce vytvoříte tabulku možností. Chcete-li zkontrolovat, zda jsou výsledky správné (pokud ne přesně, přebudujte účelovou funkci B[i][j]). Prostřednictvím vytvoření účelové funkce B[i][j] a tabulky možností budete orientovat trasování.

Tabulka možností B obsahuje n + 1 řádků, M + 1 sloupců,

  • Za prvé, vyplněno základem dynamického programování: Řádek 0 obsahuje všechny nuly.
  • Pomocí rekurzivních vzorců použijte řádek 0 k výpočtu řádku 1, použijte řádek 1 k výpočtu řádku 2 atd. … dokud nebudou vypočteny všechny řádky.
Vypočítejte tabulku možností
Tabulka možností

Sledovat

Při výpočtu tabulky možností vás zajímá B[n][M], což je maximální hodnota získaná při výběru ve všech n obalech s hmotnostním limitem M.

  • If B[n][M] = B[n – 1][M] pak balíček n není vybrán, vysledujete B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M], zjistíte, že optimální výběr má balíček n a trasování B[n – 1][M – W[n]].

Pokračujte v trasování, dokud nedosáhnete řádku 0 tabulky možností.

Algoritmus pro vyhledání vybraných balíčků v tabulce možností

Poznámka: Pokud B[i][j] = B[i – 1][j], paket i není vybrán. B[n][W] je optimální celková hodnota balíku vloženého do batohu.

Kroky pro sledování:

  • Krok 1: Počínaje i = n, j = M.
  • Krok 2: Podívejte se do sloupce j, zdola nahoru, najděte řádek i takový, že B[i][j] > B[i – 1][j]. Označit vybraný balíček i: Vyberte [i] = true;
  • Krok 3: j = B[i][j] – W[i]. Pokud j > 0, přejděte ke kroku 2, v opačném případě přejděte ke kroku 4
  • Krok 4: Na základě tabulky možností tisku vybraných balíčků.

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--;
	}
}
Funkce knapsackDyProg() in Java

Funkce knapsackDyProg() in Java

Vysvětlení kódu batohu:

  1. Vytvořte tabulku B[][]. Nastavená výchozí hodnota pro každou buňku je 0.
  2. Sestavte tabulku B[][] způsobem zdola nahoru. Vypočítejte tabulku možností pomocí vyhledávacího vzorce.
  3. Vypočítejte B[i][j]. Pokud nevyberete balíček i.
  4. Poté vyhodnoťte: pokud zvolíte balíček i, bude výhodnější než reset B[i][j].
  5. Sledujte tabulku od řádku n do řádku 0.
  6. Pokud zvolíte balíček č. Jakmile vyberete balíček n, lze přidat pouze hmotnost M – W[n – 1].


V tomto tutoriálu máte dva příklady. Zde je kód java pro spuštění výše uvedeného programu se dvěma příklady:

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

Máte výstup:

  • První příklad:
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
  • Druhý příklad:
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

Máš rád: