Problem wydawania reszty (programowanie dynamiczne)

Tutorial
Na ten temat mamy również tutorial „Problem wydawania reszty, programowanie dynamiczne”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
Problem wydawania reszty, programowanie dynamiczne (1) Przykładowe wykonanie algorytmu
REKLAMA

Marka osobista w branży IT. Jak ją zbudować i rozwijać
−40%29,94 zł
Algorytmy bez tajemnic
54,90 zł

Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.

Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.

Sformułowanie problemu

Dany jest posortowany rosnąco ciąg nominałów A=(c1, c2, …, cn) oraz kwota do wydania r. Należy wyznaczyć takie nieujemne współczynniki k1k2, …, kn, że k1c1 + k2cc + … + kncn = r, a suma k1 + k2 + … + kn jest jak najmniejsza.

Zakładamy, że wszystkie nominały i kwota r są liczbami naturalnymi, a nominał c1=1. Przyjmujemy również że wartości k nie mają górnych ograniczeń.

Opis algorytmu

Ten algorytm polega na rozstrzyganiu, czy do wydania danej kwoty opłacalne jest użycie najwyższego dostępnego nominału, czy też nie. Oznaczmy jako oi,j optymalną (najmniejszą z możliwych) liczbę monet potrzebnych do wyznaczenia kwoty i za pomocą j nominałów (c1, c2, …, cj). Aby wyznaczyć wartość oi,j musimy wiedzieć, co jest większe: oi-cj,j+1 (jedna moneta najwyższego dostępnego nominału + liczba monet potrzebna do wydania pozostałej kwoty) czy oi,j-1 (skorzystanie z rozwiązania dla mniejszego zbioru nominałów). Rozwijając to zagadnienie rekurencyjnie dojdziemy w końcu do przypadków oczywistych (np. wydanie kwoty tylko za pomocą nominału 1 lub wydanie kwoty równej jednemu z nominałów). Formalnie możemy to zapisać jako:

oi,j =

  • i dla j=1
  • 1 dla i=cj
  • oi,j-1 dla i<cj, j>1
  • min(oi,j-1, oi-cj,j+1) dla i>cj, j>1

Aby nie wyznaczać wielokrotnie tej samej wartości, wyniki należy przechowywać w następującej tabeli:

o1,1 o1,2 o1,n
o2,1 o2,2 o2,n
or,1 or,2 or,n

Warto zauważyć, że w ten sposób wyznaczamy jedynie łączną liczbę potrzebnych monet, a nie poszczególne współczynniki ki. Dlatego też w każdej komórce tabeli oprócz wartości oi,j należy zapamiętać również wartość si,j oznaczającą, od którego nominału należy rozpocząć wydawanie kwoty i. Wartości te wyznacza się następująco:

si,j =

  • 1 dla j=1
  • j dla i=cj lub jeśli wartości oi,j przypisaliśmy wartość oi-cj,j+1
  • si,j-1, jeśli wartości oi,j przypisaliśmy wartość oi,j-1

Mając wyznaczone wartości si,j poszczególne współczynniki ki można wyznaczyć w prosty sposób. Na początku wszystkim współczynnikom ki przypisujemy wartość 0. Następnie sprawdzamy wartość sr,n i zwiększamy wartość współczynnika ksr,n o 1. W kolejnym kroku zmniejszamy wartość r o csr,n i odczytujemy kolejną wartość sr,n. Czynności powtarzamy, dopóki r>0.

Tabelę z wartościami można wypełniać rekurencyjnie, jednak częściej wypełnia się ją w sposób iteracyjny (od wartości o1,1 do or,n. Jeśli tabelę wypełniamy w sposób iteracyjny kolumnami, to możemy zaoszczędzić pamięć zapamiętując tylko jedną kolumnę (nadpisując wartości zamiast zapisywania ich w kolejnej kolumnie).

Złożoność obliczeniowa

Tabela tworzona w trakcie wykonywania algorytmu ma n na r komórek, gdzie n jest liczbą nominałów a r kwotą do wydania. Złożoność czasowa algorytmu jest zatem O(nr). Złożoność pamięciowa to O(nr) jeśli pamiętamy wszystkie kolumny i O(r) jeśli je nadpisujemy.

Przykład

Załóżmy, że chcemy wyrazić kwotę 6 mając monety o nominałach 1, 3 i 4. Aby wyrazić tę kwotę za pomocą jak najmniejszej liczby monet, musimy wiedzieć, czy warto użyć monety o największym nominale (w tym przypadku 4), czy też nie. W naszym przypadku musimy zatem wiedzieć:

  1. Ile monet potrzeba do wydania kwoty 6 jedynie za pomocą nominałów 1 i 3?
  2. Ile monet potrzeba do wydania kwoty 2 za pomocą pełnej puli nominałów?

Wówczas wiemy, czy lepiej skorzystać z najwyższego dostępnego nominału, czy też wykorzystać rozwiązanie dla pomniejszonego zbioru nominałów. Aby odpowiedzieć na powyższe pytania, musimy rekurencyjnie stawiać kolejne, aż dojdziemy do przypadków oczywistych. Przygotujmy sobie zatem tabelkę, zgodnie z opisanym powyżej algorytmem. W pełni wypełniona tabela wygląda następująco:

Kwota do wydania Zbiór nominałów
1 1, 3 1, 3, 4
1 1 (1) 1 (1+0) 1 (1+0+0)
2 2 (2) 2 (2+0) 2 (2+0+0)
3 3 (3) 1 (0+1) 1 (0+1+0)
4 4 (4) 2 (1+1) 1 (0+0+1)
5 5 (5) 3 (2+1) 2 (1+0+1)
6 6 (6) 2 (0+2) 2 (0+2+0)

W każdej komórce przed nawiasem zapisaliśmy optymalną liczbę monet dla danego przypadku, a wewnątrz nawiasów liczby monet o kolejnych nominałach. W rzeczywistości dane z nawiasów nie są przechowywane w takiej postaci (zwiększyłoby to złożoność obliczeniową), a jedynie w postaci indeksu najwyższego użytego nominału. Tutaj jednak zapisaliśmy to w taki sposób po to, aby lepiej zrozumieć istotę algorytmu.

Kod źródłowy

Przykładowa implementacja algorytmu w języku C++ jest dostępna poniżej. Proszę pamiętać, że tablice w C++ są indeksowane od zera, w związku z czym indeksy elementów są nieco inne, niż jest to napisane w artykule.

void programowanieDynamiczne(int* c, int n, int r, int* k) {

	// Alokacja tymczasowych tabel
	int* o = new int[r]; // Tutaj będą optymalne liczby monet potrzebne do wydania kwoty "i"
	int* s = new int[r]; // Tutaj będą indeksy nominałów, od których należy rozpocząć wydawanie kwoty "i"

	int i, j; // Liczniki

	// Wypełnianie tabel
	for (j = 0; j < n; ++j) {

		for (i = 0; i < r; ++i) {

			if (j == 0) {

				// Rozważamy jednoelementowy zbiór nominałów - jest tylko jedna możliwość wydania kwoty
				o[i] = i + 1;
				s[i] = 0;

			}
			else if ((i + 1) == c[j]) {

				// Kwota "i" jest równa nominałowi o indeksie "j"
				o[i] = 1;
				s[i] = j;

			}
			else if ( ((i + 1) > c[j]) && (o[i] > o[i-c[j]] ) ) {

				// Należy użyć nominału o indeksie "j"
				o[i] = o[i - c[j]] + 1;
				s[i] = j; 

			} // W pozostałym przypadku pozostawiamy stare wartości o[i] i s[i]
			
		}
	}

	// Wyzerowanie tablicy k[]
	for (j = 0; j < n; ++j) {
		k[j] = 0;
	}

	// Zwiększanie wartości k na podstawie tablicy s
	while (r > 0) {
		k[s[r-1]] += 1;
		r -= c[s[r-1]];
	}

	// Zwolnienie pamięci
	delete[] o;
	delete[] s;

}

Przykładowe wywołanie funkcji:

int main()
{
	int n = 6;
	int a[6] = { 1, 3, 4, 10, 30, 40 };
	int k[6] = { 0 };
	int r = 56;

	programowanieDynamiczne(a, n, r, k);

	return 0;
}

Bibliografia

Ocena: -4 Tak Nie
Liczba głosów: 36.

Dodano: 4 października 2016 16:41, ostatnia edycja: 22 grudnia 2021 18:53.

REKLAMA

Zobacz też

Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, w skrócie NN) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną.
→ Czytaj całość

Metoda Forda-Fulkersona – algorytm służący do wyznaczania maksymalnego przepływu. Jest to algorytm bardzo ogólny, dlatego często nie jest nazywany algorytmem, a metodą. Popularną implementacją tej metody jest algorytm Edmondsa-Karpa. Algorytm można opisać następująco:

  1. Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
  2. Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
  3. Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
  4. W przeciwnym razie zwiększ przepływ w sieci (w sposób opisany w dalszej części artukułu) i wróć do punktu 1.
→ Czytaj całość

Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.

Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.

Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).

Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).

→ Czytaj całość
Polityka prywatnościKontakt