0/1 Rješavanje problema s naprtnjačom pomoću primjera dinamičkog programiranja

By: Sarah Chen Sarah Chen
Hours Ažurirano

Što je problem s naprtnjačom?

Problem s naprtnjačom algoritam je vrlo koristan problem u kombinatorici. U supermarketu ima n paketa (n ≤ 100) paket i ima težinu W[i] ≤ 100 i vrijednost V[i] ≤ 100. Lopov provali u supermarket, lopov ne može nositi težinu veću od M (M ≤ 100 ). Problem koji ovdje treba riješiti je: koje pakete će lopov odnijeti da bi dobio najveću vrijednost?

Ulazni:

  • Najveća težina M i broj paketa n.
  • Niz težine W[i] i odgovarajuće vrijednosti V[i].

Izlaz:

  • Maksimizirajte vrijednost i odgovarajuću težinu u kapacitetu.
  • Koje pakete će lopov odnijeti.

Knapsack algoritam se dalje može podijeliti u dvije vrste:

  • Problem naprtnjače 0/1 korištenjem dinamičkog programiranja. U ovom tipu algoritma Naprtnjača, svaki se paket može uzeti ili ne uzeti. Osim toga, lopov ne može uzeti djelić količine oduzetog paketa ili uzeti paket više od jednom. Ovaj tip se može riješiti pristupom dinamičkog programiranja.
  • Algoritam frakcijskog problema naprtnjače. Ovu vrstu može riješiti Greedy Strategy.

Kako riješiti problem naprtnjače pomoću dinamičkog programiranja s primjerom

U strategiji zavadi i vladaj problem koji treba riješiti dijelite na podprobleme. Podproblemi se dalje dijele na manje podprobleme. Taj zadatak će se nastaviti sve dok ne dobijete podprobleme koji se mogu lako riješiti. Međutim, u procesu takve podjele možete se mnogo puta susresti s istim problemom.

Osnovna ideja Knapsack dinamičkog programiranja je korištenje tablice za pohranjivanje rješenja riješenih podproblema. Ako se ponovno suočite s podproblemom, samo trebate uzeti rješenje u tablici bez ponovnog rješavanja. Stoga su algoritmi dizajnirani dinamičkim programiranjem vrlo učinkoviti.

Riješite problem naprtnjače pomoću dinamičkog programiranja

Za rješavanje problema dinamičkim programiranjem potrebno je izvršiti sljedeće zadatke:

  • Pronađite rješenja najmanjih podproblema.
  • Saznajte formulu (ili pravilo) za izgradnju rješenja podproblema kroz rješenja čak i najmanjih podproblema.
  • Napravite tablicu koja pohranjuje rješenja podproblema. Zatim prema pronađenoj formuli izračunaj rješenje podzadatka i spremi u tablicu.
  • Iz riješenih podproblema nalazi se rješenje izvornog problema.

Analizirajte problem naprtnjače 0/1

Kada analizirate problem 0/1 Naprtnjača pomoću dinamičkog programiranja, možete pronaći neke uočljive točke. Vrijednost algoritma naprtnjače ovisi o dva faktora:

  1. Koliko se paketa razmatra
  2. Preostala težina koju može pohraniti ruksak.

Dakle, imate dvije varijabilne količine.

S dinamičkim programiranjem imate korisne informacije:

  1. funkcija cilja ovisit će o dvije varijabilne veličine
  2. tablica opcija će biti 2-dimenzionalna tablica.

Ako je pozivanje B[i][j] najveća moguća vrijednost odabirom u paketima {1, 2, …, i} s ograničenjem težine j.

  • Najveća vrijednost kada je odabrana u n paketa s ograničenjem težine M je B[n][M]. Drugim riječima: kada postoji i paketa za odabir, B[i][j] je optimalna težina kada je najveća težina naprtnjače j.
  • Optimalna težina je uvijek manja ili jednaka maksimalnoj težini: B[i][j] ≤ j.

Na primjer: B[4][10] = 8. To znači da je u optimalnom slučaju ukupna težina odabranih paketa 8, kada postoje 4 prva paketa za odabir (od 1. do 4. paketa) i maksimalna težina naprtnjače je 10. Nije nužno da budu odabrana sva 4 predmeta.

POVEZANI ČLANCI

Formula za izračun B[i][j]

Unos, vi definirate:

  • W[i], V[i] su opet težina i vrijednost paketa i, u kojem i Formula za izračun B[i][j]{1, …, n}.
  • M je najveća težina koju naprtnjača može nositi.

U slučaju da jednostavno imate samo 1 paket na izbor. Izračunavate B[1][j] za svaki j: što znači da je najveća težina naprtnjače ≥ težina 1. paketa

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

Uz ograničenje težine j, optimalni odabiri među paketima {1, 2, …, i – 1, i} koji imaju najveću vrijednost imat će dvije mogućnosti:

  • Ako paket i nije odabran, B[i][j] je najveća moguća vrijednost odabirom među paketima {1, 2, …, i – 1} s ograničenjem težine j. Imaš:
B[i][j] = B[i – 1][j]
  • Ako je odabran paket i (naravno, uzmite u obzir samo ovaj slučaj kada je W[i] ≤ j) tada je B[i][j] jednak vrijednosti V[i] paketa i plus maksimalna vrijednost može se dobiti odabirom između paketi {1, 2, …, i – 1} s ograničenjem težine (j – W[i]). To jest, u smislu vrijednosti koju imate:
B[i][j] = V[i] + B[i – 1][j – W[i]]

Zbog stvaranja B[i][j], što je najveća moguća vrijednost, B[i][j] će biti najveća od gornje 2 vrijednosti.

Osnove dinamičkog programiranja

Dakle, morate razmisliti je li bolje odabrati paket i ili ne. Odatle imate rekurzivnu formulu kako slijedi:

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

Lako je vidjeti B[0][j] = najveća moguća vrijednost odabirom između 0 paketa = 0.

Izračunajte tablicu opcija

Gradite tablicu opcija na temelju gornje rekurzivne formule. Da biste provjerili jesu li rezultati točni (ako nisu točni, ponovno izgradite funkciju cilja B[i][j]). Kreiranjem funkcije cilja B[i][j] i tablice opcija, orijentirati ćete praćenje.

Tablica opcija B uključuje n + 1 redak, M + 1 stupac,

  • Prvo, ispunjen osnovom dinamičkog programiranja: redak 0 uključuje sve nule.
  • Koristeći rekurzivne formule, koristite redak 0 za izračun retka 1, koristite redak 1 za izračun retka 2, itd. … dok se ne izračunaju svi reci.
Izračunajte tablicu opcija
Tablica opcija

Trag

Prilikom izračuna tablice opcija zanima vas B[n][M] što je maksimalna vrijednost dobivena odabirom u svih n paketa s ograničenjem težine M.

  • If B[n][M] = B[n – 1][M] tada paket n nije odabran, vi pratite B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M], primijetili ste da optimalni odabir ima paket n i trag B[n – 1][M – W[n]].

Nastavite pratiti dok ne dođete do retka 0 tablice opcija.

Algoritam za traženje tablice opcija za pronalaženje odabranih paketa

Napomena: Ako je B[i][j] = B[i – 1][j], paket i nije odabran. B[n][W] je optimalna ukupna vrijednost paketa koji se stavlja u naprtnjaču.

Koraci za praćenje:

  • Korak 1: Polazeći od i = n, j = M.
  • Korak 2: Pogledajte u stupac j, gore od dna, pronaći ćete redak i takav da je B[i][j] > B[i – 1][j]. Označi odabrani paket i: Odaberite [i] = istina;
  • Korak 3: j = B[i][j] – W[i]. Ako je j > 0, idite na korak 2, inače idite na korak 4
  • Korak 4: Na temelju tablice opcija za ispis odabranih paketa.

Java Kodirati

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--;
	}
}
Funkcija naprtnjačaDyProg() u Java

Funkcija naprtnjačaDyProg() u Java

Objašnjenje koda naprtnjače:

  1. Napravi tablicu B[][]. Postavite zadanu vrijednost za svaku ćeliju na 0.
  2. Izgradite tablicu B[][] na način odozdo prema gore. Izračunajte tablicu opcija pomoću formule za pronalaženje.
  3. Izračunajte B[i][j]. Ako ne odaberete paket i.
  4. Zatim procijenite: ako odaberete paket i, to će biti korisnije od resetiranja B[i][j].
  5. Pratite tablicu od retka n do retka 0.
  6. Ako odaberete paket br. Nakon odabira paketa n, možete dodati samo težinu M – W[n – 1].


U ovom vodiču imate dva primjera. Evo java koda za pokretanje gornjeg programa s dva primjera:

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

Imate izlaz:

  • Prvi primjer:
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
  • Drugi primjer:
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