贪心问题——求最值问题
贪心问题一般都是求解最多或最少的最值问题，每一步总是得到当前最优解（局部最优解），若是想得到全局最优解，需要提供相关的证明。
》证明贪心法得到的当前最优解就是全局最优解：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> M = {100,5,200,10,20,1};
sort(M.begin(), M.end()); //若是未排序的则先排序
int sum = 628; //要凑齐的钱数
int count = 0; //需要的最少张数
for (int i = M.size()-1; i >=0; i--)
{
if (0==sum)
{
break; //得到了最优解就退出循环
}
int usei = sum / M[i]; //第i号钱最多能用的张数
count += usei;
sum -= usei*M[i]; //关键的，贪心后缩减总需求
}
cout << count << endl; //结果输出8
return 0;
}
image.png
