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.
[Algorytmy] Systemy kanoniczne, wydawanie reszty
-
- 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ł: 33 razy
[Algorytmy] Systemy kanoniczne, wydawanie reszty
Ostatnio zmieniony 29 maja 2012, o 18:14 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- 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
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.
Mam nadzieje, że pomogłem*D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005