Ошибка изменения кода алгоритма-монеты

Question

При заданном значении N, если мы хотим внести изменения в N центов, и у нас есть бесконечный запас каждой из монет с достоинством S = { S1, S2, .., Sm}, сколько способов мы можем внести изменение? Порядок монет не имеет значения.

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

#include <stdio.h>

int ways=0;
int remember[100] = {0};

void foo(int coin_denomination[], int size, int sum)
{
    int i;
    printf("%d\n", sum);
    if (sum==0) {
        ways++; 
        return; 
    }   
    if (remember[sum]==1)
        return; 
    remember[sum] = 1;
    if (sum < 0)
        return; 
    for(i=0;i<size;i++)
        foo(coin_denomination, size, sum-coin_denomination[i]);
}

int main()
{
    int coin_denomination[] = {1, 2, 3}; 
    int sum = 5;

    foo(coin_denomination, sizeof(coin_denomination)/sizeof(coin_denomination[0]), sum);
    printf("%d\n", ways);
    return 0;
}

Answer 1

Вам нужно изменить foo метод. Ваша проблема в том, что с переменной remember Вы не рассчитываете некоторые решения. Цель переменной remember неверно, вы используете, чтобы не обрабатывать одну и ту же коллекцию монет несколько раз, но сохраняете только сумму коллекции монет, и эту сумму можно получить с помощью нескольких коллекций монет (например: 1 1 1 иметь ту же сумму, что 1 2 когда вы выбираете второе, remember[3] будет 1 и не пройдя эту точку, пропущенное решение 1 2 2)

Другой способ не повторять coin collection в этом случае необходимо добавить параметр, представляющий индекс coin_denomination это обработка и разрешить обработку монеты только после, проблема решена.

Код (протестирован с GCC 4.9.0):

#include <stdio.h>

int ways=0;

void foo(int coin_denomination[], int size, int sum, int coin_idx = 0)
{
    if (sum < 0)
        return;
    int i;
    printf("%d\n", sum);
    if (sum==0) {
        ways++; 
        return; 
    }   
    for(i=coin_idx;i<size;i++)
        foo(coin_denomination, size, sum-coin_denomination[i], i);
}

int main()
{
    int coin_denomination[] = {1, 2, 3}; 
    int sum = 5;

    foo(coin_denomination, sizeof(coin_denomination)/sizeof(coin_denomination[0]), sum);
    printf("%d\n", ways);
    return 0;
}