0/1 Reppu-ongelman korjaus dynaamisen ohjelmoinnin esimerkillä

Mikä on selkäreppu-ongelma?

Reppu ongelma Algoritmi on erittäin hyödyllinen ongelma kombinatoriikassa. Supermarketissa on n pakettia (n ≤ 100) paketin i paino W[i] ≤ 100 ja arvo V[i] ≤ 100. Varas murtautuu supermarkettiin, varas ei voi kantaa painoa yli M (M ≤ 100) ). Tässä ratkaistava ongelma on: mitkä paketit varas ottaa pois saadakseen korkeimman arvon?

input:

Enimmäispaino M ja pakkausten lukumäärä n.
Joukko painon W[i] ja vastaavan arvon V[i].

lähtö:

Maksimoi arvo ja vastaava paino kapasiteetissa.
Mitkä paketit varas vie pois.

Selkäreppualgoritmi voidaan jakaa edelleen kahteen tyyppiin:

0/1 Reppu-ongelma dynaamisen ohjelmoinnin avulla. Tässä selkäreppu-algoritmityypissä jokainen paketti voidaan ottaa tai jättää ottamatta. Lisäksi varas ei voi ottaa murto-osaa otettua pakettia tai ottaa pakettia useammin kuin kerran. Tämä tyyppi voidaan ratkaista dynaamisella ohjelmointimenetelmällä.
Murtoreppu-ongelmaalgoritmi. Tämä tyyppi voidaan ratkaista Greedy Strategylla.

Reppu-ongelman ratkaiseminen dynaamisen ohjelmoinnin avulla esimerkin avulla

Jaa ja hallitse -strategiassa jaat ratkaistavan ongelman osaongelmiin. Aliongelmat jaetaan edelleen pienempiin osaongelmiin. Tämä tehtävä jatkuu, kunnes saat aliongelmia, jotka voidaan ratkaista helposti. Tällaisen jaon aikana saatat kuitenkin kohdata saman ongelman monta kertaa.

Knapsack-dynaamisen ohjelmoinnin perusideana on tallentaa taulukkoon ratkaistujen osaongelmien ratkaisut. Jos kohtaat aliongelman uudelleen, sinun on vain otettava taulukon ratkaisu ilman, että sinun tarvitsee ratkaista sitä uudelleen. Siksi dynaamisen ohjelmoinnin suunnittelemat algoritmit ovat erittäin tehokkaita.

Jotta voit ratkaista ongelman dynaamisen ohjelmoinnin avulla, sinun on suoritettava seuraavat tehtävät:

Etsi ratkaisuja pienimpiin osaongelmiin.
Selvitä kaava (tai sääntö) aliongelman ratkaisun rakentamiseksi pienimpienkin osaongelmien ratkaisujen avulla.
Luo taulukko, joka tallentaa osaongelmien ratkaisut. Laske sitten alitehtävän ratkaisu löydetyn kaavan mukaan ja tallenna taulukkoon.
Ratkaistuista osaongelmista löydät ratkaisun alkuperäiseen ongelmaan.

Analysoi 0/1-reppu-ongelma

Kun analysoit 0/1-reppu-ongelmaa dynaamisen ohjelmoinnin avulla, voit löytää joitain havaittavia kohtia. Reppualgoritmin arvo riippuu kahdesta tekijästä:

Kuinka monta pakettia harkitaan
Jäljellä oleva paino, jonka reppu voi säilyttää.

Siksi sinulla on kaksi muuttuvaa määrää.

Dynaamisen ohjelmoinnin avulla saat hyödyllistä tietoa:

tavoitefunktio riippuu kahdesta muuttuvasta suuresta
vaihtoehtotaulukko on kaksiulotteinen taulukko.

Jos kutsuminen B[i][j] on suurin mahdollinen arvo valitsemalla paketeista {1, 2, …, i} painorajoituksella j.

Suurin arvo valittuna n pakkauksessa painorajoituksella M on B[n][M]. Toisin sanoen: Kun valittavana on i-paketteja, B[i][j] on optimaalinen paino, kun repun maksimipaino on j.
Optimaalinen paino on aina pienempi tai yhtä suuri kuin maksimipaino: B[i][j] ≤ j.

Esimerkiksi: B[4][10] = 8. Se tarkoittaa, että optimaalisessa tapauksessa valittujen pakettien kokonaispaino on 8, kun valittavana on 4 ensimmäistä pakettia (1.-4. paketti) ja enimmäispaino reppu on 10. Kaikkia 4 tuotetta ei tarvitse valita.

Laskekaava B[i][j]

Syötä, määrität:

W[i], V[i] ovat puolestaan paketin i paino ja arvo, jossa i {1, …, n}.
M on maksimipaino, jonka reppu voi kantaa.

Siinä tapauksessa, että valittavana on vain yksi paketti. Lasketaan B[1][j] jokaiselle j:lle: mikä tarkoittaa repun maksimipainoa ≥ 1. paketin painoa

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

Painorajoituksella j optimaalisilla valinnoilla pakettien {1, 2, …, i – 1, i} joukosta suurin arvo on kaksi vaihtoehtoa:

Jos pakettia i ei ole valittu, B[i][j] on suurin mahdollinen arvo valitsemalla paketeista {1, 2, …, i – 1}, joiden painoraja on j. Sinulla on:

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

Jos paketti i valitaan (tietysti ota tämä tapaus huomioon vain, kun W[i] ≤ j), niin B[i][j] on yhtä kuin paketin i arvo V[i] plus maksimiarvo voidaan saada valitsemalla jokin seuraavista paketit {1, 2, …, i – 1} painorajoituksella (j – W[i]). Eli mitä arvoa sinulla on:

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

Koska B[i][j], joka on suurin mahdollinen arvo, on luotu, B[i][j] on maksimi kahdesta yllä olevista arvoista.

Dynaamisen ohjelmoinnin perusteet

Joten sinun on harkittava, onko parempi valita paketti i vai ei. Sieltä sinulla on seuraava rekursiivinen kaava:

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

On helppo nähdä B[0][j] = suurin mahdollinen arvo valitsemalla 0 paketti = 0.

Laske vaihtoehtotaulukko

Rakennat vaihtoehtotaulukon yllä olevan rekursiivisen kaavan perusteella. Tarkistaaksesi, ovatko tulokset oikein (jos eivät tarkalleen, rakenna tavoitefunktio B[i][j]). Luomalla tavoitefunktion B[i][j] ja vaihtoehtotaulukon suuntaat jäljityksen.

Vaihtoehtotaulukko B sisältää n + 1 riviä, M + 1 saraketta,

Ensinnäkin, täytettynä dynaamisen ohjelmoinnin perusteella: Rivi 0 sisältää kaikki nollat.
Käytä rekursiivisia kaavoja, käytä riviä 0 laskeaksesi rivin 1, käytä riviä 1 laskeaksesi rivin 2 jne. … kunnes kaikki rivit on laskettu.

Laske vaihtoehtotaulukko — Vaihtoehtotaulukko

Jäljittää

Vaihtoehtotaulukkoa laskettaessa olet kiinnostunut arvosta B[n][M], joka on maksimiarvo, joka saadaan valittaessa kaikissa n:ssä paketissa painorajoituksella M.

If B[n][M] = B[n – 1][M] silloin pakettia n ei valita, jäljität B[n – 1][M].
If B[n][M] ≠ B[n – 1][M], huomaat, että optimaalisessa valinnassa on paketti n ja jäljitys B[n – 1][M – W[n]].

Jatka jäljitystä, kunnes saavutat vaihtoehtotaulukon rivin 0.

Algoritmi vaihtoehtotaulukon etsimiseksi valittujen pakettien löytämiseksi

Huomautus: Jos B[i][j] = B[i – 1][j], pakettia i ei ole valittu. B[n][W] on reppuun laitetun pakkauksen optimaalinen kokonaisarvo.

Jäljittämisen vaiheet:

Vaihe 1: alkaen i = n, j = M.
Vaihe 2: Katso sarakkeesta j, alhaalta ylöspäin, löydät rivin i siten, että B[i][j] > B[i – 1][j]. Merkitse valittu paketti i: Valitse [i] = tosi;
Vaihe 3: j = B[i][j] – W[i]. Jos j > 0, siirry vaiheeseen 2, muussa tapauksessa siirry vaiheeseen 4
Vaihe 4: Valittujen pakettien tulostusasetustaulukon perusteella.

Java Koodi

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

Selitys selkäreppukoodille:

Luo taulukko B[][]. Aseta oletusarvo jokaiselle solulle 0.
Rakenna taulukko B[][] alhaalta ylöspäin. Laske vaihtoehtotaulukko hakukaavalla.
Laske B[i][j]. Jos et valitse pakettia i.
Arvioi sitten: jos valitset paketin i, se on hyödyllisempää kuin nollaa B[i][j].
Seuraa taulukkoa riviltä n riville 0.
Jos valitset paketin n. Kun olet valinnut paketin n, voit lisätä vain painon M – W[n – 1].

Tässä opetusohjelmassa on kaksi esimerkkiä. Tässä on java-koodi yllä olevan ohjelman suorittamiseksi kahdella esimerkillä:

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

Sinulla on tulos:

Ensimmäinen esimerkki:

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

Toinen esimerkki:

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