У меня есть неэффективная рекурсивная функция обмена монет, которая определяет количество комбинаций монет для заданной суммы. Я хотел бы преобразовать его в более эффективную итеративную функцию, если это возможно.
Одна проблема заключается в том, что я использую возврат, чтобы попробовать разные монеты в массиве, называемом номиналом. Я также использую запоминание, но это не ускоряет работу, когда сумма большая.
Вот мой код:
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? Проблема в том, что меня интересуют не все комбинации - только комбинации ровные по размеру.
Memo
? Я получаю ошибки компиляции. - person Thomas Matthews   schedule 21.06.2018change.size()
всегда увеличивается, поэтому ваш поиск заметок всегда терпит неудачу. Я не могу сказать, каков ваш алгоритм. Что вообще такоеchange
? Почему поведение меняется, когда он четного размера? Что такоеCalculate
? - person Raymond Chen   schedule 21.06.2018