Problem wydawania reszty (programowanie dynamiczne, drugi wariant)

Problem wydawania reszty, programowanie dynamiczne 2 (1) Przykładowe wykonanie algorytmu
REKLAMA

Kwalifikacja INF.03. Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych. Część 1. Projektowanie stron internetowych. Podręcznik do nauki zawodu technik informatyk i technik programista
−14%39,95 zł
Algorytmy. Ćwiczenia
34,90 zł

Ten artykuł opisuje pewną modyfikację algorytmu opartego na programowaniu dynamicznym rozwiązującego problem wydawania reszty. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego. Algorytm zaproponował J.W. Wright w pracy The Change-Making Problem (link w bibliografii).

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 k1, k2, …, 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, od którego z nominałów należy rozpocząć wydawanie kwoty. Oznaczmy jako oi optymalną (najmniejszą z możliwych) liczbę monet potrzebnych do wyznaczenia kwoty i. Aby wyznaczyć wartość oi musimy wiedzieć, która z wartości: oi-c1, oi-c2, … ,oi-cj jest najmniejsza (j jest indeksem najwyższego nominału mniejszego bądź równego i). Rozwijając to zagadnienie rekurencyjnie dojdziemy w końcu do przypadku oczywistego, jakim jest wydanie kwoty 0 za pomocą 0 monet. Formalnie możemy to zapisać jako:

oi =

  • 0 dla i=0
  • min(oi-c1, oi-c2, … ,oi-cj)+1 dla i>0 i c1, c2, …, cj ≤ i

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 należy zapamiętać również wartość si przechowującą indeks nominału, od którego należy rozpocząć wydawanie kwoty i.

Mając wyznaczone wartości si 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 i zwiększamy wartość współczynnika ksr o 1. W kolejnym kroku zmniejszamy wartość r o csr i odczytujemy kolejną wartość sr. Czynności powtarzamy, dopóki r>0.

Wartości oi można wyznaczać rekurencyjnie, jednak częściej wypełnia się ją w sposób iteracyjny (od wartości o0 do or).

Złożoność obliczeniowa

Tabela tworzona w trakcie wykonywania algorytmu ma r+1 komórek (r jest kwotą do wydania). W trakcie wypełniania każdej komórki musimy sprawdzić co najwyżej n możliwości (n jest liczbą nominałów). Złożoność czasowa algorytmu jest zatem O(nr), a złożoność pamięciowa to O(r).

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ć, od której monety najlepiej zacząć wydawanie kwoty. W naszym przypadku musimy zatem wiedzieć:

  • Ile monet potrzeba do wydania kwoty 2? (6-4=2)
  • Ile monet potrzeba do wydania kwoty 3? (6-3=3)
  • Ile monet potrzeba do wydania kwoty 5? (6-1=5)

Aby odpowiedzieć na powyższe pytania, musimy rekurencyjnie stawiać kolejne, aż dojdziemy do przypadku oczywistego (kwota równa 0 wymagająca użycia 0 monet). Aby nie stosować rekurencji, rozwiążmy problem w sposób iteracyjny, wyznaczając liczby monet potrzebnych do wydania kolejnych kwot od 0 do 6.

  • Aby wydać kwotę 0, potrzebujemy 0 monet (przypadek oczywisty).
  • Aby wydać kwotę 1, musimy użyć monety o nominale 1.
  • Aby wydać kwotę 2, musimy użyć monety o nominale 1. Zostaje wówczas do wydania kwota 1, do wydania której potrzeba 1 monety. Łącznie do wydania kwoty 2 potrzebujemy zatem 2 monet.
  • Aby wydać kwotę 3, możemy użyć monety o nominale 1 (wówczas pozostaje kwota 2 wymagająca użycia 2 monet) albo monety o nominale 3 (wówczas pozostaje kwota 0 wymagająca użycia 0 monet). Używamy więc monety o nominale 3. Do wydania kwoty 2 potrzebujemy zatem 1 monety.
  • Aby wydać kwotę 4, możemy użyć monety o nominale 1 (wówczas pozostaje kwota 3 wymagająca użycia 1 monety), monety o nominale 3 (wówczas pozostaje kwota 1 wymagająca użycia 1 monety) albo monety o nominale 4 (wówczas pozostaje kwota 0 wymagająca użycia 0 monet). Używamy więc monety o nominale 3. Do wydania kwoty 4 potrzebujemy zatem 1 monety.
  • Aby wydać kwotę 5, możemy użyć monety o nominale 1 (wówczas pozostaje kwota 4 wymagająca użycia 1 monety), monety o nominale 3 (wówczas pozostaje kwota 2 wymagająca użycia 2 monet) albo monety o nominale 4 (wówczas pozostaje kwota 1 wymagająca użycia 1 monety). Używamy więc monety o nominale 4. Do wydania kwoty 5 potrzebujemy zatem 2 monet.
  • Aby wydać kwotę 6, możemy użyć monety o nominale 1 (wówczas pozostaje kwota 5 wymagająca użycia 2 monet), monety o nominale 3 (wówczas pozostaje kwota 3 wymagająca użycia 1 monety) albo monety o nominale 4 (wówczas pozostaje kwota 2 wymagająca użycia 2 monet). Używamy więc monety o nominale 3. Do wydania kwoty 6 potrzebujemy zatem 2 monet.

Podsumowując, aby wydać kwotę 6 najpierw należy użyć monety o nominale 3. Pozostaje wówczas kwota 3, do wydania której ponownie używamy monety o nominale 3. Uzyskujemy w ten sposób rozwiązanie optymalne.

Kod źródłowy

Przykładowa implementacja algorytmu w języku C++ jest dostępna poniżej.

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

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

	int i, j, opt; // Liczniki, zmienna pomocnicza

	o[0] = s[0] = 0; // Inicjalizacja dla kwoty 0

	// Wypełnianie tabel
	for (i = 1; i <= r; ++i) {

		opt = 0;

		for (j = 1; j < n; ++j) {

			if ( (c[j] <= i) && (o[i - c[j]] <= o[i - c[opt]])) {
				opt = j;
			}
		}

		o[i] = o[i - c[opt]] + 1;
		s[i] = opt;

	}

	// 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;
		r -= c[s[r]];
	}

	// 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

  • J.W. Wright, The Change-Making Problem, JACM, Volume 22, Issue 1, 1975, s. 125-128, DOI: 10.1145/321864.321874.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 1 grudnia 2016 19:32, ostatnia edycja: 30 stycznia 2019 14:11.

REKLAMA

Zobacz też

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ść

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ść
Algorytm najmniejszej krawędzi – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną, jednak w inny sposób, niż algorytm najbliższego sąsiada. W anglojęzycznej literaturze algorytm jest najczęściej określany po prostu jako greedy algorithm (algorytm zachłanny), w skrócie GR.
→ Czytaj całość
Polityka prywatnościKontakt