# Optimal substructure with regard to making change.

Suppose we have a set of integers $\{a_1,a_2\dots,a_n\}$. with the property that any integer number is of the form $c_1a_1+c_2a_2\dots+ c_n a_n$ with all the $c's being non-negative integers. The property I am asking for is the following: what is the name of the sets$\{a_1,a_2,\dots a_n\}$such that the representation of any integer that has the least sum$c_1+c_2\dots c_n$is the one that always puts the largest numbers possible. For example: the system$1,2,4,8,16$fits the bill since the one that uses less sumands is the one where we take as many 16's first, then as many 8's and so on. I found what I was looking for here: https://math.stackexchange.com/a/200788/33907 Now I would like to know what number theoretical properties the set$\{a_1,a_2\dots,a_n\}$must have to satisfy optimal substructure with regard to making change. • I am not able to understand what you mean. I think you need to be more precise. – Jostein Trondal Feb 5 '14 at 20:37 • I don't think the set$(c_1,\dots,c_n)\$ has a special name, but just introduce it yourself and cal it 'optimal' or something like that (if needed in a proof or something similar). – Ragnar Feb 5 '14 at 20:43
• I found what I was looking for : math.stackexchange.com/a/200788/33907 – Jorge Fernández Hidalgo Feb 5 '14 at 20:47
• namely I was asking for optimal substructure with regard to making change. – Jorge Fernández Hidalgo Feb 5 '14 at 20:48