Подсчитайте количество способов внесения изменений

Question

У меня есть набор монет 1,2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000 центов. Я хочу узнать, сколько способов заплатить за определенную сумму (< = 6000). Мое текущее решение в С ++ с использованием динамического программирования нижеследовало:

long long d[6010]; 
int coin[] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}; 
d[0] = 1; 
for (int i = 0; i < 11; i++) { // iterate through all coins 
    for (int j = 1; j <= 6000; j++) 
     d[j] += d[j - coin[i]]; 
printf("%lld\n", d[20]); 

Однако мой вывод некорректный: -956301262. Это из-за проблемы с переполнением?

Answer 1

Я не вижу, как ваш алгоритм должен работать, я бы пошел рекурсивно над каждым наименованием от более высокого к нижнему (зацикливаясь на различную сумму). При использовании таблицы поиска, предположительно подобной вашей d.

Что-то вдоль линий:

howmanyways(sorted_denominations_set_starting_with_1, target amount): 
if this is already in the lookup table return the result 
else if sorted_denominations_set_starting_with_1 is {1}, then return target amount 
else loop over 0 to target amount/last_set_element 
    return the sum of results for howmanyways(sorted_denominations_set_starting_with_1 without the largest element, target amount-last_set_element*loop_index) 
keep whatever you return in the lookup table 

и возврата howmanyways ({1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}, целевое количество);

Answer 2

Ваши петли назад. Контур номинала монет должен быть вашим внутренним циклом.

Назначение вашего массива также просто не имеет смысла. В настоящее время вы просто суммируете значения изменений, которые отличаются от вашей цели конкретным наименованием монеты.

Возможно, у вас есть вектор векторов в качестве структуры данных. Каждый раз, когда вы выполняете внутренний цикл, вы должны вставлять новый вектор в свою структуру данных. Этот вектор должен представлять собой набор монет, который имеет сумму, равную интересующей стоимости.

Answer 3

Для хранения всех возможных значений вам необходимо использовать двумерный массив размером 6001x11 (в вашем случае). Начните с d [0] [0] и выполните итерацию до d [6000] [10], которая будет содержать окончательный ответ.