Преобразовать неэффективную функцию рекурсивного изменения монет в итерацию

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

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

Вот мой код:

unsigned long long CalculateCombinations(std::vector<double> &denominations, std::vector<double> change,
double amount, unsigned int index)
{
double current = 0.0;
unsigned long long combinations = 0;

if (amount == 0.0)
{
if (change.size() % 2 == 0)
{
combinations = Calculate(change);
}
return combinations;
}

// If amount is less than 0 then no solution exists
if (amount < 0.0)
return 0;

// If there are no coins and index is greater than 0, then no solution exist
if (index >= denominations.size())
return 0;

std::string str = std::to_string(amount) + "-" + std::to_string(index) + "-" + std::to_string(change.size());

auto it = Memo.find(str);

if (it != Memo.end())
{
return it->second;
}

while (current <= amount)
{
double remainder = amount - current;
combinations += CalculateCombinations(denominations, change, remainder, index + 1);
current += denominations[index];
change.push_back(denominations[index]);
}

Memo[str] = combinations;
return combinations;
}

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

* Обновление: я изменил функцию на итеративную и увеличил ее в 2 раза, чтобы использовать целые числа, но это не имело существенного значения.

Вот мой новый код:

unsigned long long CalculateCombinations(std::vector<int> &denominations, std::vector<int> change, int amount, unsigned int index)
{
unsigned long long combinations = 0;

if (amount <= 0)
return combinations;

std::stack<Param> mystack;
mystack.push({ change, amount, index });

while (!mystack.empty())
{
int current = 0;
std::vector<int> current_coins = mystack.top().Coins;
int current_amount = mystack.top().Amount;
unsigned int current_index = mystack.top().Index;
mystack.pop();

if (current_amount == 0)
{
if (current_coins.size() % 2 == 0)
{
combinations += Calculate(std::move(current_coins));
}
}
else
{
std::string str = std::to_string(current_amount) + "-" + std::to_string(current_index);
if (Memo.find(str) == Memo.end())
{
// If amount is less than 0 then no solution exists
if (current_amount >= 0 && current_index < denominations.size())
{
while (current <= current_amount)
{
int remainder = current_amount - current;
mystack.push({ current_coins, remainder, current_index + 1 });
current += denominations[current_index];
current_coins.push_back(denominations[current_index]);
}
}
else
{
Memo.insert(str);
}
}
}
}

return combinations;
}

Напоминание определяется как std :: unordered_set.

Может ли это быть решено DP? Проблема в том, что меня не интересуют все комбинации — только комбинации, которые даже по размеру.

0

Решение

Я не вижу никакой стратегии в вашем коде, которая отбрасывает деноминации.

Мой рекурсивный ответ будет на каждом рекурсивном этапе для создания 2 детей:
1 ребенок использует полный список конфессий, и тратит 1 из конечной конфессии
Второй ребенок отбрасывает ту же самую конечную деноминацию

Каждый из них рекурсивно, но во втором случае у детей есть на одну деноминацию меньше.

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

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

0

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

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

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