Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

1. If coins come in units of 1, x, and y, what is the optimal value of (x,y) that minimises the number of coins representing an arbitrary price between 1 and 149?
2.  If the number of units is now four, what is the optimal choice?

The first question is fairly easy to code

```coinz <- function(x,y){
z=(1:149)
if (y<x){xx=x;x=y;y=xx}
ny=z%/%y
nx=(z%%y)%/%x
no=z-ny*y-nx*x
return(max(no+nx+ny))
}```

and returns M=12 as the maximal number of coins, corresponding to x=4 and y=22. And a price tag of 129.  For the second question, one unit is necessarily 1 (!) and there is just an extra loop to the above, which returns M=8, with other units taking several possible values:

``` 40 11  3
 41 11  3
 55 15  4
 56 15  4
```

A quick search revealed that this problem (or a variant) is solved in many places, from stackexchange (for an average—why average?, as it does not make sense when looking at real prices—number of coins, rather than maximal), to a paper by Shalit calling for the 18¢ coin, to Freakonomics, to Wikipedia, although this is about finding the minimum number of coins summing up to a given value, using fixed currency denominations (a knapsack problem). This Wikipedia page made me realise that my solution is not necessarily optimal, as I use the remainders from the larger denominations in my code, while there may be more efficient divisions. For instance, running the following dynamic programming code

```coz=function(x,y){
minco=1:149
if (x<y){ xx=x;x=y;y=xx}
for (i in 2:149){
if (i%%x==0)
minco[i]=i%/%x
if (i%%y==0)
minco[i]=min(minco[i],i%/%y)
for (j in 1:max(1,trunc((i+1)/2)))
minco[i]=min(minco[i],minco[j]+minco[i-j])
}
return(max(minco))}
```

returns the lower value of M=11 (with x=7,y=23) in the first case and M=7 in the second one.