Geodesic
Mince zajímají nejen numismatiky
Pokroky matematiky, fyziky a astronomie, Tome 62 (2017) no. 2, pp. 110-120
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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á.
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á.
Classification : 05A17, 68Q25 
@article{PMFA_2017_62_2_a2,
     author = {Dvo\v{r}\'akov\'a, \v{L}ubom{\'\i}ra and Dohnalov\'a, Marie},
     title = {Mince zaj{\'\i}maj{\'\i} nejen numismatiky},
     journal = {Pokroky matematiky, fyziky a astronomie},
     pages = {110--120},
     year = {2017},
     volume = {62},
     number = {2},
     language = {cs},
     url = {http://geodesic.mathdoc.fr/item/PMFA_2017_62_2_a2/}
}
TY  - JOUR
AU  - Dvořáková, Ľubomíra
AU  - Dohnalová, Marie
TI  - Mince zajímají nejen numismatiky
JO  - Pokroky matematiky, fyziky a astronomie
PY  - 2017
SP  - 110
EP  - 120
VL  - 62
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/PMFA_2017_62_2_a2/
LA  - cs
ID  - PMFA_2017_62_2_a2
ER  - 
%0 Journal Article
%A Dvořáková, Ľubomíra
%A Dohnalová, Marie
%T Mince zajímají nejen numismatiky
%J Pokroky matematiky, fyziky a astronomie
%D 2017
%P 110-120
%V 62
%N 2
%U http://geodesic.mathdoc.fr/item/PMFA_2017_62_2_a2/
%G cs
%F PMFA_2017_62_2_a2
Dvořáková, Ľubomíra; Dohnalová, Marie. Mince zajímají nejen numismatiky. Pokroky matematiky, fyziky a astronomie, Tome 62 (2017) no. 2, pp. 110-120. http://geodesic.mathdoc.fr/item/PMFA_2017_62_2_a2/

[1] Adamaszek, M., Niewiarowska, A.: Combinatorics of the change-making problem. Eur. J. Comb. 31 (2010), 47–63. | DOI | MR

[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 | Zbl

[5] Heuberger, C., Prodinger, H.: On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing 66 (2001), 377–393. | DOI | MR | Zbl

[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 | MR | Zbl

[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 | Zbl

[10] Wright, J. W.: The change-making problem. J. Assoc. Comput. Mach. 22 (1975), 125–128. | DOI | Zbl