【3.1】贪心算法-解分发饼干

发布于:2024-08-23 ⋅ 阅读:(34) ⋅ 点赞:(0)

一、题目

        假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是, 每个孩子最多只能给一块饼干 对每个孩子i,都有一个 胃口值 g[i] ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j,都有一个 尺寸s[j]。如 果 s[j] >= g[i] , 我们 可 以 将 这 个 饼 干 j 分 配 给 孩 子 i , 这个孩子会得到满足 。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

示例 1:
输入 : g = [ 1 , 2 , 3 ] , s = [ 1 , 1 ]
输出 : 1
解释 :
你有三个孩子和两块小饼干, 3 个孩子的胃口值分别是: 1 , 2 , 3
虽然你有两块小饼干,由于他们的尺寸都是 1 ,你只能让胃口值是 1 的孩子满足。 所以你应该输出 1
示例 2:
输入 : g = [ 1 , 2 ] , s = [ 1 , 2 , 3 ]
输出 : 2
解释 :
你有两个孩子和三块小饼干, 2 个孩子的胃口值分别是 1 , 2
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2 。
提示:
1) 1 <= g.length <= 3*10^4
2) 0 <= s.length <= 3*10^4
3) 1 <= g[i], s[j] <= 2^31-1

二、解题思路

        贪心算法,亦称贪婪算法,是一种在解决问题时始终选择当前状态下最优解的策略。换言之,该算法并不追求全局最优,而是基于局部最优解的累积效果。

        在《算法导论》一书中,对贪心算法有如下阐述:贪心算法在每一步都做出当时认为最佳的选择,即始终采取局部最优的决策,期望这些局部最优选择能够导向全局最优解。

        针对本题,贪心算法尤为适用。题目要求尽可能多地满足孩子们的需求,由于饼干不可分割,因此我们可以采取一种策略,即让胃口较大的孩子食用较大的饼干,而胃口较小的孩子则食用较小的饼干。具体操作时,可以从胃口最小的孩子开始,尝试用最小的饼干来满足其需求,若无法满足,则逐步尝试更大的饼干,直至找到合适的饼干或遍历完所有饼干。

#include <iostream>
#include <vector>
#include <algorithm>

int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
    // 先对胃口值和饼干尺寸进行排序
    std::sort(g.begin(), g.end());
    std::sort(s.begin(), s.end());
    int count = 0;
    for (int j = 0; count < g.size() && j < s.size(); j++) {
        // 如果当前饼干能满足当前孩子的胃口值,count就加1,否则就继续查找更大的饼干
        if (g[count] <= s[j])
            count++;
    }
    return count;
}

int main() {
    std::vector<int> g = {1, 2, 3}; // 孩子的胃口值
    std::vector<int> s = {1, 1};    // 饼干的尺寸

    int result = findContentChildren(g, s);
    std::cout << "满足的孩子数量: " << result << std::endl;

    return 0;
}

三、代码实现

        还一种方式就是先从最大的饼干开始,看一下能不能满足胃口最大的,如果不能满足就 找胃口稍微小一点是再试一下,如果还不能满足就一直找。代码实现如下:
#include <iostream>
#include <vector>
#include <algorithm>

int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
    // 先对胃口值和饼干尺寸进行排序
    std::sort(g.begin(), g.end());
    std::sort(s.begin(), s.end());
    int count = 0;
    int i = s.size() - 1;
    for (int j = g.size() - 1; i >= 0 && j >= 0; j--) {
        // 如果当前饼干能满足当前孩子的胃口值,count就加1,否则就继续查找胃口更小的孩子
        if (g[j] <= s[i]) {
            count++;
            i--;
        }
    }
    return count;
}

int main() {
    std::vector<int> g = {1, 2, 3}; // 孩子的胃口值
    std::vector<int> s = {1, 1};    // 饼干的尺寸

    int result = findContentChildren(g, s);
    std::cout << "满足的孩子数量: " << result << std::endl;

    return 0;
}
        贪心算法仅追求局部最优解,它能够界定某些问题的可行域,但无法确保解的最优性。由于贪心算法始终立足于局部视角,并未全面考量整体情况,因此在某些问题上应用贪心算法是适宜的,而在其他问题上则可能不适用。这些都需要针对具体问题进行具体分析。


网站公告

今日签到

点亮在社区的每一天
去签到