Algorytmy. Ćwiczenia
34,90 zł
Projektowanie systemów rozproszonych. Wzorce i paradygmaty dla skalowalnych, niezawodnych usług
−30%27,93 zł
PHP 7. Algorytmy i struktury danych
59,00 zł
Java. Kompendium programisty. Wydanie X
179,00 zł
Opus magnum C++11. Programowanie w języku C++ (komplet)
149,00 zł
Uczenie maszynowe z użyciem Scikit-Learn i TensorFlow
89,00 zł

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 Przykładowe wykonanie algorytmu
REKLAMA

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

  1. J.W. Wright, The Change-Making Problem (link) [dostęp: 8 listopada 2017]
  2. Dynamic Programming | Set 7 (Coin Change) - GeeksforGeeks. [dostęp: 8 listopada 2017]
Ocena: 0 Tak Nie
Liczba głosów: 2.

Dodano: 4 października 2016 16:41, ostatnia edycja: 8 listopada 2017 15:24.

REKLAMA

Zobacz też

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość

Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.

Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.

Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.

Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.

→ Czytaj całość

Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.

Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.

→ Czytaj całość
Polityka prywatnościKontakt