現地で使いやすい両替

現地で使いやすい両替

締め切りが 201702/21 10:00 AM なので，その 1 分後に投稿されるように予約

設問
日本から海外旅行に行く場合は外貨に両替しますが、海外からの旅行者が日本に来るときは日本円に両替します。
このとき、現時点でのレートに従って両替しますが、使うときに便利なように、紙幣や硬貨を組み合わせます。
できるだけ現地の文化を知りたいので、多くの種類を組み合わせて両替したいところです。
今回は米ドルから日本円への両替を考えます。
紙幣や硬貨の種類の数が最大になるもののうち、全体の枚数が最小になる両替方法を求め、その全体の枚数を出力してください。
例えば、1ドル112.54円のときに100ドルを日本円に交換すると11,254円で、その交換方法として以下のような例があります。

紙幣・硬貨  例1    例2   例3   例4   例5
1万円札     1     0     0     0     0
5千円札     0     1     1     1     1
2千円札     0     0     1     2     2
千円札      1     5     3     1     1
500円玉     0     2     2     1     2
100円玉     2     1     1     4     1
50円玉      1     2     1     4     2
10円玉      0     5     9    14     4
5円玉       0     0     2     2     2
1円玉       4     4     4     4     4
枚数        9    20    24    33    19

例1は紙幣や硬貨の種類が5種類、例2は7種類なのに対し、例3〜5は9種類のため、例3〜5の中から、全体の枚数が少ない例5を選びます。
（他のパターンの中でも、例5が最小になります。）

標準入力から両替後の日本円の金額が指定されたとき、紙幣・効果の種類が最大で全体の枚数が最小になる場合を求め、その時の枚数を標準出力に出力してください。
なお、入力されるのは整数のみで、最大でも50,000とします。

【入出力サンプル】
標準入力
11254

標準出力
19

=================================================

expand.grid ですべての組み合わせを作っておき，その中で，条件を満たす場合を抽出する

f = function(y) {
    x = c(10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)
    a = expand.grid(0:4*10000, 0:1*5000, 0:5*2000, 0:2*1000, 0:2*500, 0:5*100, 0:2*50, 0:5*10, 0:2*5, 0:5)
    index = rowSums(a) == y
    a = a[index,]
    kind = rowSums(a > 0)
    n = apply(a, 1, function(z) sum(z/x))
    cat(min(n[which(kind == max(kind))]))
}

f(11254) # 19