如果你是一个班主任班上举办活动要搬运一批重量不一的货物每个人只能搬运一个货物你该怎样安排人员相信你一定会优先让力气大的男生去搬运重的货物剩下轻的货物再让力气小的女生去搬运。如果你是这样想的那么已经掌握了贪心算法的精髓只关注局部最优。贪心算法是指在解决问题时每一步都选择目前的最优解即不顾及整体最优通过局部最优推出整体最优情况。什么是贪心算法贪心算法是指在解决问题时每一步都选择目前的最优解即不顾及整体最优通过局部最优推出整体最优情况。在上面的例子中让力气小的人去搬运轻的货物其实是为了节省出更多力气大的同学去搬运更重的货物。往细了说对于货物a只需要让能搬得起货物a的同学中力气最小的同学去搬即为最优解。可以发现贪心算法的使用条件为子问题的最优解合成的全局解也为最优解。贪心算法一般可以按如下进行1.将问题分解为若干子问题2.求各个子问题的最优解3.将子问题的最优解合成为全局最优解下面是一些例题Leetcode 455 分发饼干假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是满足尽可能多的孩子并输出这个最大数值。对于这道题与刚才的搬运货物例子一样对于孩子a优先将能够满足他的饼干中的最小饼干分给他对所有孩子进行这种分配操作知道无法满足。关于分配顺序优先分配胃口小的孩子便于操作classSolution { public: int findContentChildren(vectorint g, vectorint s) { sort(g.begin(),g.end()); sort(s.begin(),s.end());//从小到大排序g和s int j 0,ans 0;//i指向g,j指向s int n g.size(); int m s.size(); for(int i 0;i n;i) { while(j m s[j] g[i]) j;//从前j位置向后寻找第一个 //能够满足g[i]的s[j] if(j m)//还有饼干符合要求进行分配 { j; ans; } else//没有饼干符合要求退出 break; } return ans; } };Luogu P1223 排队接水有 n 个人在一个水龙头前排队接水假如每个人接水的时间为 T[i]请编程找出这 n 个人排队的一种顺序使得 n 个人的平均等待时间最小。一个人的等待时间不包括他的接水时间。如果两个人接水的时间相同编号更小的人应当排在前面。对于本题易想到耗时少的人排在前面时总耗时更少所以对数组进行排序即可由于有接水时间相同的情况使用结构体解决#includebits/stdc.h using namespace std; typedef longlong ll; int n; struct stu{ ll no; ll t; }; stu a[1005]; double pre 0; double ans 0; bool cmp(stu s1,stu s2) { if(s1.t ! s2.t) return s1.t s2.t; else return s1.no s2.no; } int main() { cin n; for(int i 1;i n;i) { cin a[i].t; a[i].no i; } sort(a 1,a 1 n,cmp); for(int i 1;i n;i) { cout a[i].no ; ans pre; pre a[i].t;//注意是平均“等待时间” } printf(\n%.2lf,ans / n); return 0; }使用贪心算法时一定要注意子问题的最优解是否能够合成全局最优解不然就会犯“见树木不见森林”的错误”。