DouKaku?

いま、あなたの財布の中にはコインがたくさん入っています。これを少しでも減らしたいと思います。

支払うべき金額と持っているコインの種類と数を与えられたときに、どのコインを何枚出せばおつりを受け取った後のコインの数が最も少なくなるか返す関数を作ってください。おつりは最も枚数が少なくなる方法で渡されます。

例えば、1円玉2枚、10円玉4枚、100円玉3枚を持っていて、147円支払う場合、 1円玉2枚と100円玉2枚を渡して50円玉1枚と5円玉1枚を受け取るのが2枚減で最も枚数を減らせます。Pythonで表現するならば下のような挙動をする関数を作ってください。

>>> pay(147, {1: 2, 10: 4, 100: 3})
{1: 2, 100: 2}

2007-07-01追記：　　minkeさんの指摘通り、「手元にある全てのコインを渡せば、結果としてもっとも枚数が少なくなる」 ので、「渡した硬貨がおつりで返ってくるような渡し方は禁止」と条件を追加します。