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 Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
19,90 zł
Czysty kod. Podręcznik dobrego programisty
69,00 zł
Gotowanie dla geeków. Wydanie II
−30%48,30 zł
Kwalifikacja EE.09. Programowanie, tworzenie i administrowanie stronami internetowymi i bazami danych. Część 1. Tworzenie stron internetowych. Podręcznik do nauki zawodu technik informatyk
47,00 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ą nominałów (c1, c2, …, cj). Aby wyznaczyć wartość oi,j musimy wiedzieć, co jest większe: oi-aj,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: 0 Tak Nie
Liczba głosów: 2.

Dodano: 4 października 2016 16:41, ostatnia edycja: 30 stycznia 2019 13:52.

REKLAMA

Zobacz też

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość

Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).

Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:

  • Jak rozwiązać przypadek bazowy (trywialny).
  • Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.

Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.

→ 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