Problem wydawania reszty (programowanie dynamiczne, drugi wariant)

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

Tworzenie aplikacji z wykorzystaniem GPT-4 i ChatGPT. Buduj inteligentne chatboty, generatory treści i fascynujące projekty
−40%35,40 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ż

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość

Algorytm Zhanga-Suena – algorytm służący do szkieletyzacji obrazu binarnego. Szkieletyzacja polega na wyborze z obrazu binarnego tych pikseli, które są równo odległe od krawędzi obiektu.

→ 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ść
Polityka prywatnościKontakt