一个可运行的贪心算法分饼干C++
时间: 2024-03-13 07:45:51 浏览: 22
好的,这是一个典型的贪心算法问题。假设有m个孩子和n个饼干,每个孩子都有一个贪心因子g[i],每个饼干都有一个大小s[j]。我们需要将饼干分配给孩子,使得满足贪心条件的孩子个数最大。具体的思路如下:
1. 将孩子和饼干按照贪心因子和大小从小到大排序。
2. 从第一个孩子和第一个饼干开始,依次比较孩子的贪心因子和饼干的大小,如果饼干的大小可以满足孩子的贪心因子,就将这个饼干分配给这个孩子,并且继续考虑下一个孩子和下一个饼干;否则就考虑下一个饼干是否可以满足这个孩子的贪心因子,直到找到一个合适的饼干或者没有合适的饼干为止。
3. 继续考虑下一个孩子和下一个饼干,直到所有的孩子都被分配了饼干或者没有合适的饼干为止。
下面是一个可运行的C++代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0;
while (i < g.size() && j < s.size()) {
if (g[i] <= s[j]) {
i++;
}
j++;
}
return i;
}
int main() {
vector<int> g = {1, 2, 3};
vector<int> s = {1, 1};
cout << findContentChildren(g, s) << endl; // 输出1
g = {1, 2};
s = {1, 2, 3};
cout << findContentChildren(g, s) << endl; // 输出2
return 0;
}
```
其中,g为贪心因子数组,s为饼干大小数组,函数返回可以满足的孩子个数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)