| Title:
|
Mince zajímají nejen numismatiky (Czech) |
| Title:
|
Coins are of interest not only for numismatists (English) |
| Author:
|
Dvořáková, Ľubomíra |
| Author:
|
Dohnalová, Marie |
| Language:
|
Czech |
| Journal:
|
Pokroky matematiky, fyziky a astronomie |
| ISSN:
|
0032-2423 |
| Volume:
|
62 |
| Issue:
|
2 |
| Year:
|
2017 |
| Pages:
|
110-120 |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| Summary:
|
V článku představíme dva druhy úloh týkajících se platby mincemi, které souvisejí s optimalitou počtu použitých mincí. V případě problému platby (říká se také rozměňování — anglicky change making problem), tj. skládání částky z mincí bez možnosti vracení, jsou úlohy spojené s optimalitou dobře prozkoumané. Analogické úlohy zformulujeme pro směnu, tj. skládání částky z mincí s možností vracení. Zde zůstává naopak řada problémů otevřená. (Czech) |
| MSC:
|
05A17 |
| MSC:
|
68Q25 |
| . |
| Date available:
|
2017-07-10T08:48:28Z |
| Last updated:
|
2018-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/146814 |
| . |
| Reference:
|
[1] Adamaszek, M., Niewiarowska, A.: Combinatorics of the change-making problem., Eur. J. Comb. 31 (2010), 47–63. MR 2552590, 10.1016/j.ejc.2009.05.002 |
| Reference:
|
[2] Balková, Ľ., Šťastná, A.: Jsou české mince optimální?. Rozhledy matematicko-fyzikální 90 (2015), 14–22. |
| Reference:
|
[3] Cai, X.: Canonical coin systems for change-making problems.. International Conference on Hybrid Intelligent Systems 1 (2009), 499–504. |
| Reference:
|
[4] Heuberger, C.: Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms.. Period. Math. Hung. 49 (2004), 65–89. Zbl 1072.11007, MR 2106466 |
| Reference:
|
[5] Heuberger, C., Prodinger, H.: On minimal expansions in redundant number systems: Algorithms and quantitative analysis.. Computing 66 (2001), 377–393. Zbl 1030.11003, MR 1842756, 10.1007/s006070170021 |
| Reference:
|
[6] Kleber, M., Shallit, J., Vakil, R.: What this country needs is an 18¢ piece.. Math. Intell. 25 (2003), 20–23. |
| Reference:
|
[7] Kozen, D., Zaks, S.: Optimal bounds for the change-making problem.. Theoret. Comput. Sci. 123 (1994), 377–388. Zbl 0801.68079, MR 1256208, 10.1016/0304-3975(94)90134-1 |
| Reference:
|
[8] Lueker, G. S.: Two NP-complete problems in nonnegative integer programming.. Technical Report TR-178, Computer Science Laboratory, Department of Electrical Engineering, Princeton University, March 1975. |
| Reference:
|
[9] Pearson, D.: A polynomial-time algorithm for the change-making problem.. Oper. Res. Lett. 33 (2005), 231–234. Zbl 1177.90350, MR 2108270 |
| Reference:
|
[10] Wright, J. W.: The change-making problem.. J. Assoc. Comput. Mach. 22 (1975), 125–128. Zbl 0314.90067, 10.1145/321864.321874 |
| . |
