Problem wydawania reszty (programowanie dynamiczne, drugi wariant)

Problem wydawania reszty, programowanie dynamiczne 2 (1) Przykładowe wykonanie algorytmu
REKLAMA C++. Algorytmy i struktury danych
−29%72,77 zł
Czysty kod. Podręcznik dobrego programisty
−30%48,30 zł
Java. Kompendium programisty. Wydanie X
−30%125,30 zł
Mistrz czystego kodu. Kodeks postępowania profesjonalnych programistów
−30%27,30 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ż

Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.

Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.

→ Czytaj całość

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną.

→ Czytaj całość

Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.

W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:

Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:

Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.

Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.

→ Czytaj całość
Polityka prywatnościKontakt