C++ 搬水果贪心算法实现代码

C++搬水果贪心算法实现代码的攻略如下：

什么是贪心算法？

贪心算法（Greedy Algorithm）又称贪心策略，是指在利用当前信息的情况下，做出当下最优的选择。贪心算法不会考虑到全局的最优解，而只关注当下的最优解。贪心算法在求解最优解的过程中，通常需要证明其正确性，并且使用贪心算法求得的解不一定是全局最优解，但是可以得到比较优秀的近似解。

搬水果问题的贪心策略

搬水果问题的场景是这样的：有m个果篮，每个果篮最多放n个水果，有k个水果需要放入果篮，每个水果的重量为w[i]，每个果篮最多承载重量为c。为了最省力地搬运水果，需要考虑如何将水果分配到果篮中。我们可以用贪心算法解决这个问题。

首先，将水果按照重量从大到小排序；

然后，按照排好序的顺序把水果依次放入每个果篮中，如果放入当前果篮后，果篮所承载的水果重量超过了c，则新开一个果篮继续放入水果；

最后，返回果篮的数量即可。

代码实现如下：

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 100010;

int n, m, k, c;
int w[N];

bool cmp(int a, int b){
    return a > b;
}

int main(){
    scanf("%d %d %d %d", &n, &m, &k, &c);
    for(int i = 0; i < k; ++i) scanf("%d", &w[i]);
    sort(w, w + k, cmp);  // 按照重量从大到小排序
    int res = 0;
    priority_queue<int> q;
    for(int i = 0; i < k; ++i){
        if(q.size() < n){  // 还有空篮子，则直接放入
            q.push(w[i]);
        }
        else{  // 没有空篮子，则看能不能放到已有的篮子中
            int x = q.top();  // 取出当前承重最大的篮子
            q.pop();  // 移除篮子
            x += w[i];  // 将当前水果加入篮子
            q.push(x);  // 将篮子放回
        }
    }
    while(q.size()){  // 统计篮子数量
        if(q.top() <= c) res++;
        q.pop();
    }
    printf("%d\n", res);
    return 0;
}

示例说明

假设有4个篮子，每个篮子最多放2个香蕉，现有6个香蕉，重量分别为10, 8, 5, 4, 3, 2。篮子的承重量为15，如果使用贪心策略，需要将香蕉放入篮子中，求出最少需要几个篮子？

按照贪心策略，根据香蕉重量从大到小排序后，首先把重量最大的香蕉(10)放入篮子中；然后将重量第二大的香蕉(8)放入篮子中；此时篮子已经满了，需要另开一个篮子，将重量第三大的香蕉(5)放入新开的篮子中，此时篮子数为2；接着将重量第四大的香蕉(4)放入之前较轻的篮子中，此时篮子数仍为2；以此类推，将剩下的两个香蕉放入篮子中后，一共使用了2个篮子。

假设有3个篮子，每个篮子最多放3个橘子，现有7个橘子，重量分别为5, 4, 3, 2, 1, 1, 1。篮子的承重量为9，如果使用贪心策略，需要将橘子放入篮子中，求出最少需要几个篮子？

按照贪心策略，根据橘子重量从大到小排序后，首先把重量最大的橘子(5)放入篮子中；然后将重量第二大的橘子(4)放入篮子中；此时篮子已经满了，需要另开一个篮子，将重量第三大的橘子(3)放入新开的篮子中，此时篮子数为2；接着将剩下的4个橘子(2,1,1,1)依次放入已有的篮子中，篮子数仍为2；总共使用了2个篮子。