我有一个低效的递归硬币更改功能,可以计算给定金额的硬币组合数量 . 如果可能的话,我想将其转换为更有效的迭代函数 .
一个问题是我使用回溯来尝试在称为面额的数组中的不同硬币 . 我也在使用memoization但是当数量很大时它不会加快速度 .
这是我的代码:
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解决吗?问题是我对所有组合都不感兴趣 - 只有大小合适的组合 .
1 回答
我没有在您的代码中看到任何丢弃宗派的策略 .
我的递归回答是在每个递归阶段创建2个孩子:
1个孩子使用完整的面额列表,并花费1个结束面额
第二个孩子丢弃相同的结束面额
他们各自递归,但在第二种情况下,孩子们有一个较少的面额与之合作 .
我相信返回的结果都是截然不同的,但是当然你会得到一个痛苦的情况,你可以在10000以上的水平上获得100美元的便士 . 这可以很容易地优化,当你达到1面额时,可能表明最好在每一轮处理和丢弃更高面额而不是更低的面额 .
您还可以检测所有剩余面额是彼此的简单倍数并快速生成排列而不进行完全递归的情况:生成最小硬币集(每个高面额的最大值)然后向后工作用更小的硬币数替换每个硬币 .