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=(c₁, c₂, …, c_n) oraz kwota do wydania r. Należy wyznaczyć takie nieujemne współczynniki k₁, k₂, …, k_n, że k₁c₁ + k₂c_c + … + k_nc_n = r, a suma k₁ + k₂ + … + k_n jest jak najmniejsza.

Zakładamy, że wszystkie nominały i kwota r są liczbami naturalnymi, a nominał c₁=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 o_i,j optymalną (najmniejszą z możliwych) liczbę monet potrzebnych do wyznaczenia kwoty i za pomocą j nominałów (c₁, c₂, …, c_j). Aby wyznaczyć wartość o_i,j musimy wiedzieć, co jest większe: o_i-cj,j+1 (jedna moneta najwyższego dostępnego nominału + liczba monet potrzebna do wydania pozostałej kwoty) czy o_i,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:

o_i,j =

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

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

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

s_i,j =

• 1 dla j=1
• j dla i=c_j lub jeśli wartości o_i,j przypisaliśmy wartość o_i-cj,j+1
• s_i,j-1, jeśli wartości o_i,j przypisaliśmy wartość o_i,j-1

Mając wyznaczone wartości s_i,j poszczególne współczynniki k_i można wyznaczyć w prosty sposób. Na początku wszystkim współczynnikom k_i przypisujemy wartość 0. Następnie sprawdzamy wartość s_r,n i zwiększamy wartość współczynnika k_sr,n o 1. W kolejnym kroku zmniejszamy wartość r o c_sr,n i odczytujemy kolejną wartość s_r,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 o_1,1 do o_r,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).

REKLAMA

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:

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

REKLAMA

Bibliografia

• J.W. Wright, The Change-Making Problem, JACM, Volume 22, Issue 1, 1975, s. 125-128, DOI: 10.1145/321864.321874.
• Coin Change | DP-7, geeksforgeeks.com [Dostęp 2019-01-25].