难币兑换算法

Question

我正在尝试建立一个交换算法，以交换与库存相同数量的硬币。我有一个字典，其中包含命名为& &;金额

输入是要返回的值，例如€2,80我需要一个算法来计算把股票考虑在内的最佳返还方式。
(最好的方法是库存硬币的剩余数量具有最低的标准偏差，这意味着所有面额的库存是相同的)所以在这个例子中，我需要返回1,20欧元的硬币&10克拉，因为2克拉和50克拉的硬币几乎缺货。在这种情况下，最佳输出是:

{200, 0}, 
{100, 2}, 
{50, 0}, 
{20, 3},
{10, 2}

我如何使用c++算法计算每个面额的最佳返回数并保持所有硬币的库存相同?

#include <map>
static map<int, int, greater<int>> ValueAmount = {
{200, 3}, 
{100, 20}, 
{50, 2}, 
{20, 15},
{10, 14}
};
std::map<int, int> PayoutAlgorithm(std::map<int, int> ValueAmount, long amountToPay){

}
int main(int argc, char** argv){
...
bool succes = ReturnMoney(PayoutAlgorithm());
...
return 1;
}

其中map ValueAmount是一个键值对。关键是硬币的面额，价值是硬币的数量。

Answer 1

解决这类问题的方法是把它分解成更容易理解的东西。

1. 我们对我们的数据结构满意吗?坦率地说，我会使用一个类来保存数量和计数，而不是两个不同的数组，但这就是我。

2. 确定我需要给他们多少(在你的最低值-无浮点数)。例如，127美分。

3. 开始分发硬币，从最大面额开始，然后往下。例如，1磅硬币，25美分硬币和21美分硬币。

4. 如果你用完了一种特定的硬币，那么你必须使用更多的下一个较低面额的硬币。