0

したがって、典型的な硬貨の両替問題では、額面 x1、x2、...、xn の無制限の硬貨を使用して値 v を両替できるかどうかを判断する必要があります。各コインを最大1回使用しても同じ問題がありますか?

元の問題については、値のプレフィックスを繰り返し処理して、v-x_i を変更できるかどうかを確認できることはわかっていますが、金種ごとに最大で 1 つのコインに制限されている場合、途方に暮れています。

始めるためのヒントはありますか？宗派の接頭辞を繰り返し処理できると思っていたのかもしれません。確かではありませんが...

4

2 に答える 2

0

コインの両替問題では、順方向または逆方向の再帰を使用できます。ur ステートメントでは、u は逆方向に使用されます。ここで forward メソッドを与えます。UNLIMITED バージョンと AT-MOST-ONCE バージョンを簡単に解決できます。

f が 1D ブール配列であるとします。f[i] は、u が値 i を変更できるかどうかを意味します。最初は、f[0]=true、その他は false です。

無制限のバージョン:

for (int i=1;i<=n;i++)
    for (int j=0;j<v;j++)
        if (f[j])
            f[j+x[i]]=true;

AT-MOST-ONCE バージョン:

for (int i=1;i<=n;i++)
    for (int j=v-1;j>=0;j--)
        if (f[j])
            f[j+x[i]]=true;

唯一の違いは、ループ j の順序です。

理解に役立つ例：

コストが 2 のコインが 1 種類だけあるとします。つまり、x[1]=2 です。そして v=10

最初のアルゴリズムの後、f[0]=f[2]=f[4]=f[6]=f[8]=f[10]=true を得ることができます。

しかし、2 番目のアルゴリズムでは、f[0]=f[2]=true しか取得できません。

于 2013-01-25T03:46:41.960 に答える