0

使用できるコインの最小数を計算するような方法で、コイン変更の問題を解決しようとしました。http://www.algorithmist.comのアルゴリズムの投稿を使用しました。アルゴリズムは次のとおりです。

C(N,m) = min(C(N,m - 1),C(N - Sm,m) + 1)

with the base cases:

    C(N,m) = 1,N = 0
    C(N,m) = 0,N < 0
    C(N, m) = 0, N >= 1, m <= 0

しかし、コードを書くと無限に実行されます。

コードは次のとおりです。

#include <iostream>
#include <algorithm>
using namespace std;
int Types[101];
int  Coins(int N, int m)
{
    if(N==0)
    {
        return 1;
    }
    else if(N<0)
    {
        return 0;
    }
    else if(N>0 && m<=0)
    {
        return 0;
    }
    else
    {
        int a = Coins(N,m-1);
        int b = Coins(N-Types[m],m) + 1;
        int c = min(a,b);
        return c;
    }
}

 int main()
{
    int noOfCoins, Target;
    cin >> noOfCoins >> Target;
    for(int i = 0; i<noOfCoins; i++)
    {
        cin >> Types[i];
    }
    cout << Coins(Target, noOfCoins);
    return 0;
}

何が間違っている可能性がありますか？

4

1 に答える 1

3

そのはずcout << Coins(Target, noOfCoins - 1);

それ以外のcout << Coins(Target, noOfCoins);

それ以外の場合は、0要素にアクセスしており、ここで何度も同じ状態に移動します。

int b = Coins(N-Types[m],m) + 1;

于 2013-03-30T14:51:14.860 に答える