問題
コインが複数種類あり、それらの金額が与えられる。各金額のコインは無尽蔵にあるとする。1~Xまでのすべての金額を支払えるようにコインを選ぶとき、このコインの枚数を最小化せよ。
やりかた
公式解説を参考にしました。
ある時点で選んだコインの総額がSで、かつ1~Sまでをすべて表現できるようなとき、次にS+1より大きい金額のコインを選んでしまうと、S+1が表現できなくなる。なのでS+1以下で最大のコインを選ぶことによって、それまでの数字をきちんと表現できつつ、少ないコインの枚数でなるべく大きな金額まで表現できる。この工程を総和がX以上になるまで繰り返す。
ソースは略。