[Algorytmy] Systemy kanoniczne, wydawanie reszty

patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 32 razy

[Algorytmy] Systemy kanoniczne, wydawanie reszty

Post autor: patry93 » 14 maja 2012, o 19:46

Witam.
Wiadomo, że algorytm zachłanny nie zawsze daje optymalny wynik w problemie wydawania reszty, jednak istnieją systemy monetarne, zwane kanonicznymi, w którym postępowanie zachłanne zawsze da optymalny wynik (np. dobór nominałów taki, jaki mamy w Polsce). Czy mógłby mnie ktoś nakierować na odpowiednie prace, artykuły traktujące o tym? Jak najbardziej mogą być po angielsku.
W szczególności interesowałby mnie dowód, dlaczego tak się dzieje w naszym systemie oraz jak wyglądają warunki, dzięki którym dany system staje się kanoniczny.
Ostatnio zmieniony 29 maja 2012, o 18:14 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

marcin_smu
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 21 lut 2011, o 20:49
Płeć: Mężczyzna
Lokalizacja: Skierniewice
Pomógł: 10 razy

[Algorytmy] Systemy kanoniczne, wydawanie reszty

Post autor: marcin_smu » 15 maja 2012, o 00:33

Znalazłem coś takiego:
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 \(\displaystyle{ O(n^3)}\) gdzie \(\displaystyle{ 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.
*D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005
Mam nadzieje, że pomogłem

ODPOWIEDZ