algorithm - 有限数の金種のカウント変更を解決するためのアルゴリズムはありますか？

Question

無限の数の金種のコイン交換問題を解決するアルゴリズムを知っていますが、DPを使用して有限の数の金種のアルゴリズムはありますか？

Answer 1

はい。初期アルゴリズムを変更して、その金種の利用可能なコインの数を超えるコインを追加しようとしたときに、代わりに追加しないようにします。次に、有効なコンボのみを印刷します。

もう1つのより簡単な方法は、アルゴリズムを制限なしで実行し、無効な組み合わせに基づいて出力をフィルタリングすることです。このように考えると、問題が実際に解決可能であることが本当に明白になります。