Matematyka.pl

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.

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