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

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

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. Это из-за проблемы переполнения?

1

Решение

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

2

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

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

1

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

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

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

1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector