Подсчитайте количество способов внести изменения
У меня есть набор монет 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. Это из-за проблемы переполнения?
Решение
Вы должны использовать двумерный массив размером 6001×11 (в вашем случае) для хранения всех возможных значений. Начните с d [0] [0] и повторяйте до d [6000] [10], который будет содержать окончательный ответ.
Другие решения
Я не понимаю, как ваш алгоритм должен работать, я бы рекурсивно проходил по каждой деноминации от более высокой к более низкой (перебирая разные суммы). При использовании справочной таблицы, вероятно, похож на ваш 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}, целевое количество);
Ваши петли назад. Цикл достоинства монеты должен быть вашей внутренней петлей.
Ваше назначение массива также просто не имеет смысла. В настоящее время вы просто суммируете значения изменений, которые отличаются от вашей цели определенным достоинством монеты.
Вы, вероятно, должны иметь вектор векторов в качестве структуры данных. Каждый раз, когда вы выполняете свой внутренний цикл, вы должны вставлять новый вектор в вашу структуру данных. Этот вектор должен представлять собой набор монет, сумма которых равна стоимости интереса.