алгоритм — переполнение стека изменения монет

Я попытался решить проблему замены монет таким образом, чтобы вычислить минимальное количество монет, которое можно использовать. Я использовал алгоритм пост на 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;
}

Что может быть не так?

0

Решение

Так должно быть cout << Coins(Target, noOfCoins - 1);

вместо cout << Coins(Target, noOfCoins);

В противном случае вы получаете доступ к 0 элемент, и перейдите в то же состояние снова и снова здесь:

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

3

Другие решения

Других решений пока нет …