贪心：钱币找零问题(C++)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

贪心是一种算法范例，它一点一点地构建解决方案，总是选择下一个提供最明显和最直接好处的部分。因此，选择局部最优也会导致全局解的问题最适合贪心问题。

例如，考虑分数背包问题。局部最优策略是选择权重比最大的项。这个策略也导致了全局最优解。

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有a,b,c,d,e,f,g张。现在要用这些钱来支付m元，至少要用多少张纸币？用贪心算法的思想,每一次选择最大面值的钱币。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> Num{ ,,,,,, }, Value{ ,,,,,, };int BagsQues(int money) {
int sum = ;
for (int i = Value.size() - ; i >= ; --i) {
int N = min(money / Value[i], Num[i]);
money = money - N * Value[i];
sum += N;
if (money == )
return sum;
} return -;
}int main()
{
int money;
cin >> money;
int m = BagsQues(money);
cout << m << endl; system("PAUSE");
return ;
}

求出每张面额，用了多少张：

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>using namespace std;vector<int> Num{ ,,,,,, }, Value{ ,,,,,, };vector<tuple<int, int> > BagsQues(int money) {
int sum = ;
vector<tuple<int, int> > ch;
for (int i = Value.size() - ; i >= ; --i) {
int N = min(money / Value[i], Num[i]);
money = money - N * Value[i];
sum += N;
if (N != ) {
ch.push_back({ Value[i], N });
}
if(money == )
return ch;
}
ch.clear();
ch.push_back({ -, - });
return ch;
}int main()
{
int money;
cin >> money;
vector<tuple<int, int> > m = BagsQues(money);
for (int i = ; i < m.size(); ++i) {
cout << get<>(m[i]) << ":" << get<>(m[i]) << endl;
} system("PAUSE");
return ;
}