CodeIQ 目指せお釣りマスター！を解きました

今回は商品10個、商品を渡す順番とお金の渡し方を考えます。

実行時間は1300msくらいでした。
10->20件にすると約5分かかります。

解説記事を見てみると、まだまだ工夫の余地がありそうです。
以下はいただいたコメントです。

最適解を求めるだけでなく、アルゴリズムに工夫もあって素晴らしいです！
大規模な問題になると、探索順序はプログラムの性能に大きく影響してくると思います。その辺は私自身もまだ研究中なのでよくわかりませんが、もうちょっと考えてみるつもりです。
もし良いアイデアが思いついたら教えてください。

とはいえ、@ozy4dmさんさんはRubyで0.1秒とのことなのでなかなか悔しいです。

100商品でといた人はいるんでしょうか？