Problem wydawania reszty (programowanie dynamiczne, drugi wariant)

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

Analityk danych. Przewodnik po data science, statystyce i uczeniu maszynowym
−35%44,85 zł
Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
29,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: -3 Tak Nie
Liczba głosów: 9.

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

REKLAMA

Zobacz też

Graf – struktura G = (V, E) składająca się ze skończonego zbioru wierzchołków V oraz skończonego zbioru krawędzi E, gdzie każda krawędź e ∈ E jest dwuelementowym zbiorem wierzchołków u, v ∈ V. Wierzchołki u, v połączone krawędzią e = {u, v} określane są sąsiednimi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawiać rożnego rodzaju relacje pomiędzy obiektami.

Powyższa definicja dotyczy grafu nieskierowanego, gdzie relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

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

Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.

→ Czytaj całość
Polityka prywatnościKontakt