给定美元金额将其转换为欧元硬币和纸币。你得到美元 金额作为论据，并表示美元兑欧元的汇率为1.30。你被给予 欧元计价是 500 钞票、200 钞票、100 钞票、50 钞票、20 钞票、10 钞票、5 钞票、2 钞票，1张钞票，50美分，25分，10美分，5美分，2美分，1美分。转换那个 美元金额转化为最少数量的钞票和硬币。(转换数字美元 金额(例如 10.00 美元(等值的欧元纸币和硬币。
免责声明：这是我得到的家庭作业问题。
我考虑过使用 while 循环来解决它，该循环遍历每个面额并从值中减去它。 像这样：
while(amount > 0){
if(amount - denomination[index] > 0) {
amount -= denomination[index];
}else{
index++;
}
}
但其他消息来源告诉我，硬币变化问题可以通过动态规划来解决。我很困惑。
对于这个特定的命名集更改问题，可以通过贪婪的方法解决，就像你所做的那样。
对于值相差两次的集合(如 1,2,4,8...(也是如此，但规则并不简单，正如@Patrick87注释中注意到的那样。适当的货币系统被称为"规范的"，但要找到给定的系统是否是规范的并不容易：讨论的例子
对于任意值，贪婪方法可能会失败
([1,5,15,20]为sum=30提供20+5+5，而15+15更好(
这就是为什么一般来说硬币变化问题应该用动态规划来解决
这个答案可能不够"学术"，但使用 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>传统上，像呈现给您的货币硬币变化问题被设计为动态编程问题。下面是一个例子，你的方法将在更简单的前提下为类似问题产生错误的答案：
给定无限数量的 7 美元钞票、5 美元钞票、4 美元钞票和 1 美元钞票，以及价格为 N$ 的某个项目，找到购买该物品的最佳方式，以便您使用尽可能少的钞票。
现在，如果我在上一个问题中设置N=12，您将看到您的算法确实会将 12$ 分解为 1 个 7$ 的账单和另一个 5$ 的账单。但是，如果我设置N=9，那么您会注意到您的算法会将 9$ 分解为一张 7 美元的账单和两张 1$ 的账单，而最佳解决方案是一个 5$ 的账单和一个 4$ 的账单。
那么，您的解决方案是否正确？事实证明，确实如此。这仅仅是因为您的账单是以您贪婪的解决方案始终有效的方式给出的(我测试了它高达 100000.00$ 只是为了 100% 确定(。我相信你可以在网上找到资源，这些资源可以告诉你为什么你的账单价值集与贪婪的算法一起工作，不幸的是，我无法为你提供一个令人满意的解释。这是与此问题相关的讨论
虽然你可以用贪婪的算法来解决你的解决方案，但动态规划(DP(方法也会产生正确的答案，幸运的是，有很多资源可以教你关于DP，如果这是让你感到困惑的地方，比如GeeksForGeeks。如果您在实现 DP 解决方案时遇到问题，请在此处发布代码！
一般来说，在硬币系统中确定最佳表示的问题是弱NP困难的。可能，对于世界上所有当代硬币系统，贪婪算法都可以正常工作。大多数当代硬币系统使用所谓的二进制十进制模式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。我写了一个程序来检查这一点：
#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，因此整套面额都适合贪婪算法。