货币金额如何换算变化？

Question

Given a dollar amount convert it into euro coins and bills. You are given the dollar amount as the argument, and said that the dollar to euro rate is 1.30. You are given that euro denomations are 500 bill, 200 bill, 100 bill, 50 bill, 20 bill, 10 bill, 5 bill, 2 bill, 1 bill, 50 cents, 25 cents, 10 cents, 5 cents, 2 cents, 1 cent. Convert that dollar amount into the least amount of bills and coins. (Convert a numerical dollar amount (such as .00) to an equivalent amount in Euro Bills and Coins.)

免责声明：这是我布置的作业。

我考虑过使用 while 循环来解决它，该循环遍历每个面额并将其从值中减去。类似于：

while(amount > 0){
  if(amount - denomination[index] > 0) {
     amount -= denomination[index];
  }else{
     index++;
  }
}

但是其他消息来源告诉我硬币找零问题是用动态规划解决的。我很困惑。

Answer 1

对于这个特定的面额设置更改问题可能会像您一样通过贪心法解决。

对于值相差两次（如 1、2、4、8...）的集合也是如此，但规则并不简单，正如 @Patrick87 在评论中注意到的那样。适当的货币系统称为 "canonical"，但要确定给定系统是否规范并不容易：example of discussion

对于任意值，贪心法可能会失败
（[1,5,15,20] sum=30 的 20+5+5 而 15+15 更好）

这就是为什么一般的硬币找零问题应该用动态规划来解决的原因

Answer 2

传统上，货币硬币找零问题（如呈现给您的问题）设计为动态规划问题。下面是一个示例，其中您的方法将对具有更简单前提的 similar 问题产生错误答案：

Given an unlimited number of 7$ bills, 5$ bills, 4$ bills and 1$ bills, and a certain item with price of N$, find the optimal way of purchasing the item so that you use the least amount of bills possible.

现在，如果我在上一题中设置 N=12，您会发现您的算法确实会将 12 美元分解为 1 张 7 美元的钞票和另一张钞票5 美元。但是，如果我设置 N=9，那么您会注意到当最佳解决方案是一张 5 美元的钞票和一张 4 美元的钞票。

那么你的解法正确吗？事实证明，是的。这仅仅是因为您的帐单是以您的 greedy solution will always work (I tested it up to 100000.00$ just to be 100% sure). I'm sure you can find resources online that can tell you the exact reason as to why your set of bill values works with a greedy algorithm, and unfortunately, I can't provide you with a satisfying explanation. Here's a discussion 与此问题相关的方式给出的

虽然您可以使用贪心算法求解您的解决方案，但动态规划 (DP) 方法也会产生正确的答案，幸运的是，有大量资源可以教您有关 DP 的知识，如果那是什么把你搞糊涂了，比如GeeksForGeeks. If you're having issues implementing the DP solution, the code is posted here!

Answer 3

在硬币系统中确定最佳表示的问题通常是 weakly NP-hard。也许，对于世界上所有当代硬币系统来说，贪婪算法都可以正常工作。大多数现代硬币系统使用所谓的二进制十进制模式 1-2-5。但是您的示例有 25 美分，需要仔细查看。

但首先，让我们证明 1-2-5 模式适用于贪心算法。观察他们的 LCM 是 10，这意味着我们只需要检查 [1..9].

中的数字

1 = 1,0,0  4 = 0,2,0  7 = 0,1,1
2 = 0,1,0  5 = 0,0,1  8 = 1,1,1
3 = 1,1,0  6 = 1,0,1  9 = 0,2,1

所以，这个模式是贪心的。现在让我们将注意力转向前六个面额 50、25、10、5、2、1。这里我们有相同的 LCM - 50。我写了 a program 来检查这个：

#include <iostream>
#include <array>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <iterator>

bool IsOptimal(const int sum, const int numberOfCoins, std::array<int, 6>::const_iterator begin, std::array<int, 6>::const_iterator end) {
    if (sum < 0 || numberOfCoins == 0) return true;
    for (auto it = begin; it < end; ++it) {
        const int nextSum = sum - *it;
        if (nextSum == 0) return numberOfCoins == 1;
        if (!IsOptimal(nextSum, numberOfCoins - 1, it, end))
            return false;
    }
    return true;
}

int main() {
    const std::array<int, 6> kDenoms = { 1,2,5,10,25,50 };
    for (int i = 1; i < 50; ++i) {
        std::array<int, 6> change = { 0 };
        int sum = 0;
        while (sum != i) {
            auto it = std::upper_bound(kDenoms.cbegin(), kDenoms.cend(), i - sum);
            ++change[--it - kDenoms.cbegin()];
            sum += *it;
        }
        const bool isOptimal = IsOptimal(sum, std::accumulate(change.cbegin(), change.cend(), 0), kDenoms.cbegin(), kDenoms.cend());
        std::cout << std::setw(2) << i << ": ";
        std::copy(change.cbegin(), change.cend() - 1, std::ostream_iterator<int>(std::cout, ","));
        std::cout << change.back() << " " << std::boolalpha << isOptimal << std::endl;
    }
    return 0;
}

所以，基本上，我们知道什么？我们知道所有小于50的数量我们都可以用贪心算法攻击得到它的最优解。

观察，所有50以上的面额都可以被50整除，所以不会干扰50、25、10、5、2、1。我们也证明了贪心算法适用于模式1-2-5 , 所以整组面额都适用于贪心算法。

Answer 4

这个答案可能 "academic" 不够，但是使用 JavScript 可以将其归结为 Array.reduce() 的简单应用（假设 "greedy" 方法适用，它对于欧元货币系统将是):

change=amnt=>(c,d,i)=>{var rest=amnt%d;
 if (rest!=amnt) {c[i]=(amnt-rest)/d; amnt=rest;}
 return c };

var rate=110.36; // Euro cents per USD
var res=document.querySelector('#result');

document.querySelector('#USD').onkeyup=ev=>{
 var cents=Math.round(ev.target.value*90.78); // amount in Euro cents
 var denom=[50000,20000,10000,5000,2000,1000,
            5000,2000,1000,500,100,50,20,10,5,2,1];
 var coins=denom.reduce(change(cents),[]);

 res.innerHTML=cents/100+' €<br>'
   +coins.map((n,i)=>n+'x'+(denom[i]>99?denom[i]/100+'€':denom[i]+'ct'))
         .filter(v=>v).join(', ');
}

USD <input type="text" value="13" id="USD">
<div id="result"></div>

货币金额如何换算变化？

How to convert currency amount to change?

algorithm

coin-change