有趣网站建设无聊微信网站协议书

贪心算法实例-问题分析

饼干分配问题

有一群孩子和一堆饼干，每个小孩都有一个饥饿度，每个饼干都有一个能量值，当饼干的能量值大于等于小孩的饥饿度时，小孩可以吃饱，求解最多有多少个孩子可以吃饱?(注:每个小孩只能吃一整块饼干)如饼干能量值[6,3,1,2],小孩饥饿度[1,5,3]，此时最多能有三个小孩可以吃饱。
贪心策略:让最容易吃饱的小孩先选择，从所有饼干中选择，能量值最小的饼干。

贪心思路

先对饼干和孩子的饥饿度进行排序。

然后从最小的饥饿度的孩子开始，尝试用能量值最小的饼干去满足。如果该饼干能满足当前孩子的需求，则分配给他；否则，尝试下一个饼干。

这样，优先满足最容易吃饱的孩子，保证尽可能多的孩子得到饼干。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 分配饼干函数
int findContentChildren(vector<int>& children, vector<int>& cookies) {// 对饥饿度和饼干进行排序sort(children.begin(), children.end());sort(cookies.begin(), cookies.end());int childIndex = 0; // 孩子索引int cookieIndex = 0; // 饼干索引// 贪心算法进行匹配while (childIndex < children.size() && cookieIndex < cookies.size()) {// 如果当前饼干能满足当前孩子if (cookies[cookieIndex] >= children[childIndex]) {childIndex++;  // 孩子得到了饼干}cookieIndex++;  // 无论如何都要尝试下一个饼干}return childIndex;  // 返回得到饼干的孩子数量
}int main() {// 输入数据vector<int> children = {1, 5, 3};  // 孩子的饥饿度vector<int> cookies = {6, 3, 1, 2};  // 饼干的能量值// 调用函数，输出结果int result = findContentChildren(children, cookies);cout << "最多有 " << result << " 个孩子可以吃饱。" << endl;return 0;
}

运行结果