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.
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ń.
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ą j nominałów (c1, c2, …, cj). Aby wyznaczyć wartość oi,j musimy wiedzieć, co jest większe: oi-cj,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 =
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 =
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).
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.
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ć:
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.
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; }
Dodano: 4 października 2016 16:41, ostatnia edycja: 22 grudnia 2021 18:53.
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.
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).