Проблема смены монет C ++ - PullRequest
Новая
       10

Проблема смены монет C ++

0 голосов
/ 16 марта 2011

У меня проблема с написанием динамического алгоритма для решения проблемы с обменом монет, вот что я получил:

arr [значение] - глобальный массив, заполненный 0, длина значения, которое я хочу решить;

a [n] - массив со значениями монет; 

void dynamic(int n, int *a, int value) {
arr[0]=0;
for(int i=1;i<value;i++){;
    for(int j=0;j<n;j++){
        if(i==arr[j]) arr[i]=1;
        else{
            arr[i] = arr[i-1] + 1;          
        }
    }
}}

Я знаю, как я хочу это сделать, но я не знаю, как это реализовать.

Пример:
Допустим, у меня есть монеты 1 4 10 15 40 и значение 37 для решения. Я заполняю обр как это:
если ценность монеты = i, я делаю arr [i] = 1; для следующих элементов, пока я ниже следующей монеты, я ставлю предыдущее значение + 1, обр [i-1] + 1.
Это должно заполнить arr [i] следующим образом: 1 = 1, 2 = 2, 3 = 3, 4 = 1, 5 = 2 и т. Д., Но я что-то упускаю и не знаю, как правильно его заполнить Я хочу.

Может ли кто-нибудь помочь сделать это так, как я хочу? Я пытался понять это, но ничего, что я нашел, не является правильным. Я даже написал весь алгоритм с использованием рекурсии, но он слишком медленный, поэтому мне нужно писать все заново.

1 Ответ

0 голосов
/ 16 февраля 2013

Возможно, вы захотите: 

memset(arr,0,sizeof(arr));
arr[0]=1;
for(int i=0;i<n;++i)
    for(int j=a[i];j<value;++j)
        arr[j]+=arr[j-a[i]];

Это должно быть правильно, если я вас правильно понимаю, в основном это ловкий трюк для реализации рекурсии ... 

f[i,j]=f[i-1,j]+f[i-1,j-a[i]];

Очевидно, что это занимает O(n Value) время.

...