Wprowadzenie do zachłanności i dynamiki

18.10.2010 - Łukasz Zatorski
Trudność

Wydawanie Reszty

Kasa Załóżmy że naszemu bohaterowi udało się uporać z zadaniem i na swoim dzielnym wierzchowcu dotarł z powrotem do miasta z plecakiem pełnym łupów. Resztą drobnych opłacił pobyt w gospodzie (stajnia gratis) i czym prędzej udał się sprzedać zdobycze. Kupiec którego znalazł dysponuje on mnóstwem monet w jakiejś określonej walucie o różnej wartości. Z pewnością na wypłacenie należności ich wystarczy, ale kupiec musi postępować rozsądnie – inaczej przy jakiejś okazji, może mu braknąć któregoś z nominałów. Stara się zatem zapłacić za łupy przy użyciu jak najmniejszej ilości monet.

Problem ten spotykamy na co dzień w trochę innej postaci – w trakcie wydawania reszty w sklepach, bankach czy automatach z napojami (pod taką nazwą jest też znany w fachowej literaturze i pracach naukowych). Mając do wydania 174 złote nie trudno zgadnąć w jaki sposób użyć najmniejszej ilości banknotów i monet – wybieramy (zachłannie!) największe możliwe nominały:

Jest to jednak proste wyłącznie dlatego że współczesne systemy monetarne zostały zaprojektowane w nieprzypadkowy sposób. Takie systemy w których kierowanie się zachłannym wyborem zawsze daje optymalne rozwiązanie nazywamy kanonicznymi.

Załóżmy że dla urozmaicenia i uczczenia jakiegoś ważnego wydarzenia (lub by przynieść szczęście milionom obywateli) wprowadzono do obiegu obok standardowych nominałów monetę 7złotową. Mając do wydawania resztę w wysokości 14 złotych i kierując się naszą zachłanną metodą, zdecydowalibyśmy się na użycie banknotu 10złotowego i dwóch 2złotówek. Tymczasem wystarczyły dwie sztuki świeżo wybitej monety 7złotowej!

Historycznym przykładem podobnej, a nawet bardziej skomplikowanej sytuacji był system monetarny funkcjonujący w Wielkiej Brytanii do roku 1971 (z podziałem na szylingi, floreny i korony) oraz wiele walut stosowanych na przestrzeni wieków w Imperium Rzymskim i innych starożytnych cywilizacjach.

Szukamy analogii

Co zatem zrobić w wypadku, gdy nominały nie są dla nas tak przyjazne lub komuś wyjątkowo zależy na monecie 7złotowej Rozwiązywanie zadań algorytmicznych często opiera się na korzystaniu ze zdobytej wiedzy i szukaniu analogii. Spróbujmy dostrzec podobieństwo do znanego już problemu. Zachłanne wybieranie największego nominału przypomina zachowanie barbarzyńcy przy wybieraniu łupów. Może tutaj też dałoby się znaleźć jakąś dynamiczną metodę tak jak miało to miejsce w przypadku pakowania plecaka?

Ponownie użyjemy pól reprezentujących nasze podproblemy – możliwe kwoty, które potrafimy wydać. Zawartością pola będzie pusta jeśli kwoty nie da się osiągnąć, a w przeciwnym wypadku – będzie wpisana tam najmniejsza liczba monet, przy których jest to możliwe.

Zamiast „wagi” przedmiotu, pojawiającej się w plecaku mamy wartość jednej monety. Zamiast „wartości” przedmiotów, mamy ilość monet. Dodatkowo przy każdej poprawie naszej tablicy zapisujemy sobie, przy jakiego rodzaju monecie otrzymaliśmy lepsze rozwiązanie. Monety o tym samym nominale możemy stosować wielokrotnie. W przeciwieństwa do pakowania plecaka, przeglądamy pola od najmniejszych do największych – w ten sposób uwzględniamy na bieżąco wprowadzone przez nas poprawki:

Odzyskiwanie wyniku wydawania reszty jest dużo prostsze niż w przypadku pakowaniu plecaka, gdzie w celu uniknięcia wykorzystania dwa razy tego samego przedmiotu byliśmy zmuszeni do dwuwymiarowej tablicy pomocniczej. Ponownie zaczynamy w stanie odpowiadającym interesującej nas kwocie, a następnie wypisujemy kolejne nominały, cofając się o wskazywane przez nie wartości:

Ostatni

W trakcie implementacji rozwiązania na komputerze (w popularnym języku imperatywnym) wystarczy wykorzystać to, co uznaliśmy wcześniej za błąd, to znaczy użyć pętli rosnącej. Można wtedy zauważyć wyraźne podobieństwo obu problemów:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MSIZE = 1000, PUSTO=1001;
int ilosc,reszta,nominal,kwoty[MSIZE]; /*kolejno: ilosc przedmiotow,reszta 
do wydania, aktualny nominał, tablica do metody dynamicznej*/
int main(){
  cin >> ilosc >> reszta;
  for(int j=1;j <= reszta;j++) kwoty[j]=PUSTO;
  kwoty[0]=0;
  for(int i=0;i < ilosc;i++){
    cin >> nominal;
    for(int j=0;j < reszta;j++) 
      if(kwoty[j]!=PUSTO){
        int nowa_kwota = j + nominal;
        int nowa_ilosc = kwoty[j]+1;
        if((nowa_kwota <= reszta) && (nowa_ilosc < kwoty[nowa_kwota])) 
                  kwoty[nowa_kwota] = nowa_ilosc;
      }
  }
  if(kwoty[reszta]==PUSTO) cout << "NIE DA SIĘ"; 
  else cout << kwoty[reszta];
}

Dla bardzo ambitnych:

Istnieją wydajne sposoby określania, czy podany zbiór nominałów jest systemem kanonicznym. D. Pearson* w swojej pracy naukowej podał schemat algorytmu o złożoności $ O(n^3) $ gdzie $ n $ jest liczbą monet. Korzysta ona między innymi z nierówności ograniczającej najmniejszy kontrprzykład dla którego zachłanny wybór nie jest optymalny, jeśli taki istnieje.


Mam nadzieję drogi czytelniku że już teraz wiesz, co łączy pakowanie plecaka z wydawaniem monet. Proponuję zdobytą wiedzę wykorzystać w praktyce, ale niekoniecznie rozpoczynając błyskotliwą karierę złodzieja! Wybory zachłanne i dynamiczne planowanie stosuje się przy wielu innych problemach optymalizacyjnych - w fabryce części komputerowych, firmie kurierskiej czy w trakcie układania planu szkolnego. Jeśli zaś chciałbyś zostać zawodnikiem i mierzyć się z nimi na rozgrywkach informatycznych, spróbuj swoich sił rozwiązując zadania dołączone do tego artykułu.




*D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005

4.846155
Twoja ocena: Brak Ocena: 4.8 (13 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com