Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
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á.
References:
[1] Adamaszek, M., Niewiarowska, A.: Combinatorics of the change-making problem. Eur. J. Comb. 31 (2010), 47–63. DOI 10.1016/j.ejc.2009.05.002 | MR 2552590
[2] Balková, Ľ., Šťastná, A.: Jsou české mince optimální?. Rozhledy matematicko-fyzikální 90 (2015), 14–22.
[3] Cai, X.: Canonical coin systems for change-making problems. International Conference on Hybrid Intelligent Systems 1 (2009), 499–504.
[4] Heuberger, C.: Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms. Period. Math. Hung. 49 (2004), 65–89. MR 2106466 | Zbl 1072.11007
[5] Heuberger, C., Prodinger, H.: On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing 66 (2001), 377–393. DOI 10.1007/s006070170021 | MR 1842756 | Zbl 1030.11003
[6] Kleber, M., Shallit, J., Vakil, R.: What this country needs is an 18¢ piece. Math. Intell. 25 (2003), 20–23.
[7] Kozen, D., Zaks, S.: Optimal bounds for the change-making problem. Theoret. Comput. Sci. 123 (1994), 377–388. DOI 10.1016/0304-3975(94)90134-1 | MR 1256208 | Zbl 0801.68079
[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.
[9] Pearson, D.: A polynomial-time algorithm for the change-making problem. Oper. Res. Lett. 33 (2005), 231–234. MR 2108270 | Zbl 1177.90350
[10] Wright, J. W.: The change-making problem. J. Assoc. Comput. Mach. 22 (1975), 125–128. DOI 10.1145/321864.321874 | Zbl 0314.90067
Search
Partner of
