Here you will find daily news and tutorials about R, contributed by over 750 bloggers.
There are many ways to follow us - By e-mail:On Facebook: If you are an R blogger yourself you are invited to add your own R content feed to this site (Non-English R bloggers should add themselves- here)

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?

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

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:

[1] 40 11 3
[1] 41 11 3
[1] 55 15 4
[1] 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

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

Related

To leave a comment for the author, please follow the link and comment on their blog: R – Xi'an's Og.