已知，中华人民共和国的纸币面额分别为：100元、50元、20元、10元、5元、2元、1元，输入钱数，输出最小的货币方案。
int main() { int value[7] = { 100, 50, 20, 10, 5, 2, 1 }, count[7], change; int i, j, sum; while (cin >> change, change) { for (i = 0; i < 7; i++) { count[i] = change / value[i]; change -= count[i] * value[i]; } sum = 0; for (i = 0; i < 7; i++) { cout <<"value:" <<value[i]<<"===>>count:"<<count[i]<<endl; sum += count[i]; } cout << "totalCount:" << sum << endl; } return 0; }
贪心算法在这里之所以总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。
int main() { int value[11], count[11], change; int i, n, sum; while (cin >> n >> change) { for (i = 1; i <= n; i++) { cin>>value[i]; } sort(value + 1, value + 1 + n);//# include<algorithm> for (i = n; i >= 1; i--) { count[i] = change / value[i]; change -= count[i] * value[i]; } sum = 0; for (i = n; i >= 1; i--) { cout <<"value:" <<value[i]<<"===>>count:"<<count[i]<<endl; sum += count[i]; } cout << "totalCount:" << sum << endl; } return 0; }
可惜的是，一个问题满足什么样的条件才能保证贪心算法可以得出最优解，对于这个问题，目前还没有一个好的判定方法。即：你只能证明你的方法满足贪心算法的两个基本要素：最优子结构性质和贪心选择性质，所以求出的解是最优解；但你不能证明这个问题用其他的贪心策略也能得出正确解。
原文：http://www.cnblogs.com/mmcmmc/p/3878695.html
