贪心：assign cookies分糖果

首页 > 贪心：assign cookies分糖果

贪心：assign cookies分糖果

贪心算法的核心：

遵循某种规律，使用最少的资源来完成目标

所以在了解贪心算法的时候需要明确两点

寻找共有的规律
每一步的迭代使用最优的策略（消耗最少的资源）

问题如下：

已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s >= 某个孩子的需求因子g时，代表该糖果可以满足该孩子;求使用这些糖果，最多能满足多少孩子?(注意，某个孩子最多只能用1个糖果满足)

类似：g = [2, 5, 9, 9, 10, 15] ，糖果大小：s = [1, 3, 6, 8, 20]

根据贪心算法的核心分析：

规律

假如糖果大小不满足一个孩子的需求因子，则比该需求因子更小的都不会被满足

使用最小的糖果能够满足孩子，则可以留下较大的糖果满足更高需求因子的孩子
迭代策略

使用较小的糖果满足来满足较小需求因子的孩子

实现如下（文末有完整测试代码）：

/*
需要注意：一个糖果满足了一个孩子之后就不能满足其他的孩子了
*/
int allocate_num(vector<int> &child, vector<int> &candy) { if(child.size() == 0 || candy.size() == 0) { return 0;}/*根据规律，调整糖果大小和需求因子的序列*/sort(child.begin(),child.end()); sort(candy.begin(),candy.end());int child_num = 0;int candy_num = 0;/*迭代策略：只有糖果大小 >= 孩子的需求因子之后才能算满足*/while(child_num < child.size() && candy_num < candy.size()) { if(candy[candy_num] >= child[child_num]) { child_num ++;}candy_num ++;}/*返回可以分配给孩子的数量*/return child_num;
}

测试代码如下:

#include 
#include 
#include using namespace std;int allocate_num(vector<int> &child, vector<int> &candy) { if(child.size() == 0 || candy.size() == 0) { return 0;}sort(child.begin(),child.end());sort(candy.begin(),candy.end());int child_num = 0;int candy_num = 0;while(child_num < child.size() && candy_num < candy.size()) { if(candy[candy_num] >= child[child_num]) { child_num ++;}candy_num ++;}return child_num;
}int main() { vector<int> child;vector<int> candy;int tmp_child;int tmp_candy;cout << "input child " << endl;for (int i = 0;i < 5; ++i) { cin >> tmp_child;child.push_back(tmp_child);}cout << "input candy " << endl;for (int i = 0;i < 5; ++i) { cin >> tmp_candy;candy.push_back(tmp_candy);}cout << "the num of child can be allocate is " << allocate_num(child,candy) << endl;return 0;
}

输入输出如下:

input child 
2 5 9 9 10
input candy 
1 3 6 8 20
the num of child can be allocate is 3

贪心：assign cookies分糖果

更多相关：

leetcode-402 移掉K位数组

大数的减法函数--c语言

hdu 1085 Holding Bin-Laden Captive!

NYOJ--811--变态最大值

C# 生成系统唯一号

leetcode-135 分发糖果