Изменение монеты: количество решений, когда заказ имеет значение, когда заказ не имеет значения

Я решил проблему замены монет с помощью динамического программирования с помощью следующих функций count_distinct и count_perm, которые дают количество решений для данной суммы денег (параметр x) и используемых монет (параметр c). Вектор d используется для запоминания: он записывает количество решений для каждой неотрицательной суммы денег, то есть для значений {0,1, …, x}.

Например, когда сумма денег равна 5, а используемые монеты — {2, 3, 4}, count_distinct дает результат 1 (он считает решения {2, 3} и {3, 2} равными), и count_perm дает результат 2 (он рассматривает их как разные решения).

Я не понимаю причину, почему это происходит. В двух функциях переменные цикла расположены в противоположном порядке, но я не понимаю, почему это должно иметь значение. Кроме того, индексация в count_distinct заботится о том, чтобы отрицательные суммы денег не оценивались, и соответствующая проверка выполняется с помощью оператора continue в count_perm.

#include <iostream>
#include <vector>

using namespace std;

long count_distinct(int x, vector <long> c) {

vector <long> d(x+1);
d[0] = 1;
int k = c.size();

for (int i = 0; i < k; i++) {
for (int j = c[i]; j <= x; j++) {
d[j] += d[j - c[i]];
}
}
return d[x];
}

long count_perm(int x, vector <long> c) {

vector <long> d(x + 1);
d[0] = 1;
int k = c.size();

for (int i = 1; i <= x; i++) {
for (int j = 0; j < k; j++) {
if (i - c[j] < 0) continue;
d[i] += d[i - c[j]];
}
}
return d[x];
}

int main() {
int x = 5;
vector <long> c;
c.push_back(2);
c.push_back(3);
c.push_back(4);

long distinct = count_distinct(x, c);
long perms = count_perm(x, c);
cout << distinct << endl;
cout << perms << endl;
return 0;
}

0

Решение

Задача ещё не решена.

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

Других решений пока нет …

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