Combinatorics of the change-making problem

Anna Maria Adamaszek; Michal Jan Adamaszek

doi:10.1016/j.ejc.2009.05.002

Combinatorics of the change-making problem

Anna Maria Adamaszek, Michal Jan Adamaszek

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

15 Citationer (Scopus)

Abstract

We investigate the structure of the currencies (systems of coins) for which the greedy change-making algorithm always finds an optimal solution (that is, a one with minimum number of coins). We present a series of necessary conditions that must be satisfied by the values of coins in such systems. We also uncover some relations between such currencies and their sub-currencies. ?? 2009 Elsevier Ltd. All rights reserved.

Originalsprog	Engelsk
Tidsskrift	European Journal of Combinatorics
Vol/bind	31
Udgave nummer	1
Sider (fra-til)	47-63
Antal sider	17
ISSN	0195-6698
DOI	https://doi.org/10.1016/j.ejc.2009.05.002
Status	Udgivet - 2010
Udgivet eksternt	Ja

Adgang til dokumentet

10.1016/j.ejc.2009.05.002

Citationsformater

@article{41e67c11a9ff4251bd8c5647e8e6d88a,

title = "Combinatorics of the change-making problem",

abstract = "We investigate the structure of the currencies (systems of coins) for which the greedy change-making algorithm always finds an optimal solution (that is, a one with minimum number of coins). We present a series of necessary conditions that must be satisfied by the values of coins in such systems. We also uncover some relations between such currencies and their sub-currencies. ?? 2009 Elsevier Ltd. All rights reserved.",

author = "Adamaszek, {Anna Maria} and Adamaszek, {Michal Jan}",

year = "2010",

doi = "10.1016/j.ejc.2009.05.002",

language = "English",

volume = "31",

pages = "47--63",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "1",

}

TY - JOUR

T1 - Combinatorics of the change-making problem

AU - Adamaszek, Anna Maria

AU - Adamaszek, Michal Jan

PY - 2010

Y1 - 2010

N2 - We investigate the structure of the currencies (systems of coins) for which the greedy change-making algorithm always finds an optimal solution (that is, a one with minimum number of coins). We present a series of necessary conditions that must be satisfied by the values of coins in such systems. We also uncover some relations between such currencies and their sub-currencies. ?? 2009 Elsevier Ltd. All rights reserved.

AB - We investigate the structure of the currencies (systems of coins) for which the greedy change-making algorithm always finds an optimal solution (that is, a one with minimum number of coins). We present a series of necessary conditions that must be satisfied by the values of coins in such systems. We also uncover some relations between such currencies and their sub-currencies. ?? 2009 Elsevier Ltd. All rights reserved.

U2 - 10.1016/j.ejc.2009.05.002

DO - 10.1016/j.ejc.2009.05.002

M3 - Journal article

VL - 31

SP - 47

EP - 63

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

IS - 1

ER -