如何转换货币金额以进行更改？[副本]

Question

给定一美元金额，将其转换为欧元硬币和纸币。你得到了美元金额作为论据，并说美元对欧元的汇率是1.30。你可以看到欧元的名称是500美元，200美元，100美元，50美元，20美元，10美元，5美元，2美元，1美元，50美分，25美分，10美分，5美分，2美分，1美分。将该美元金额转换为最小金额的纸币和硬币。（将数字美元金额（如10.00美元）转换为等值的欧元纸币和硬币。）

免责声明：这是我收到的家庭作业问题。

我想过用一个同时循环来解决它，它迭代每个面额，并从值中减去它。类似于：

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

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

Answer 1

传统上，货币硬币变化问题，如向您展示的问题，被设计为动态编程问题。这里有一个例子，你的方法会在一个更简单的前提下对一个类似的问题给出错误的答案：

给定无限数量的7美元钞票、5美元钞票、4美元钞票和1美元钞票，以及价格为N美元的某项商品，找到购买该商品的最佳方式，以便您使用尽可能少的钞票。

现在，如果我在上一个问题中设置N=12，您将看到您的算法确实将12美元分解为1张7美元的钞票和另一张5美元的钞票。然而，如果我设置N=9，那么你会注意到你的算法将把9美元分解成一张7美元的钞票和两张1美元的钞票，而最优解是一张5美元的钞票和一张4美元的钞票。

那么你的解决方案正确吗？事实证明，它是。这仅仅是因为你的账单是以一种你贪婪的解决方案永远有效的方式给出的（我测试了1000.00美元，只是为了100%确定）。我相信你可以在网上找到资源，可以告诉你为什么你的一组账单值与贪婪的算法一起工作的确切原因，不幸的是，我不能给你一个令人满意的解释。下面是有关这个问题的讨论

虽然你可以用贪婪的算法解决你的问题，但是动态编程（DP）方法也会产生正确的答案，幸运的是，如果你感到困惑，有很多资源可以教你关于DP的知识，比如GeeksForGeeks。如果您在实现DP解决方案时遇到问题，代码将发布在此处！

Answer 2

这个答案可能不够“学术”，但是使用JavScript，你可以把它归结为一个简单的Array.reduce（）应用程序（假设“贪婪”方法适用，这将适用于欧元货币体系）：

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>

Answer 3

对于这个特定的面额集更改问题可能会通过贪婪的方法来解决，就像您所做的那样。

对于值相差两倍的集合也是如此，比如1,2,4,8...，但是规则并不简单，正如@Patrick87在评论中注意到的那样。适当的货币系统被称为“规范的”，但要找到给定的系统是否规范并不容易：讨论的例子

对于任意值，贪婪方法可能失败
（[1,5,15,20]为sum=30提供2055，而1515更好）

这就是为什么一般来说硬币兑换问题应该用动态规划来解决