C++ 贪心算法：快递装载问题

题目描述

有一批快递要装上一辆载重量为 c 的快递车进行运送。第 i 个快递的重量为 Wi。由于每件快递都很小，几乎不占快递车的空间，但是都比较重。为了节省成本，因此需要考虑在装载体积不受限制的情况下，将尽可能多的快递装上快递车，请你编程帮助快递小哥求出来最多能装载多少件快递。

输入描述

第一行共两个整数 N，c，表示快递的件数和快递车的载重量。

第二行共有 N 个整数，分别表示快递的重量 Wi。

输出描述

共一行，输出 1 个整数，表示最多能装载的快递件数。

样例1

输入 8 400 100 200 50 90 150 50 20 80

输出 6

提示

对于 100% 的数据，N≤100，c≤10000。

代码示例

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N, c;
    cin >> N >> c;
    int w[N];
    for (int i = 0; i < N; i++) {
        cin >> w[i];
    }
    // 将快递按照重量从小到大排序
    sort(w, w + N);
    int count = 0;
    int sum = 0;
    // 从最轻的快递开始依次装载
    for (int i = 0; i < N; i++) {
        if (sum + w[i] <= c) {
            sum += w[i];
            count++;
        } else {
            break;
        }
    }
    cout << count << endl;
    return 0;
}

思路

首先将快递按照重量从小到大排序。然后从最轻的快递开始依次装载，直到快递车的载重量达到上限或者所有快递装载完毕。

具体步骤如下：

输入 N 和 c。
输入快递的重量，并将其存储在一个数组中。
将数组按照升序排序。
使用一个变量 count 记录已经装载的快递件数，初始值为 0。
使用一个变量 sum 记录已经装载的快递的总重量，初始值为 0。
从数组的第一个元素开始遍历：
- 如果当前快递的重量加上 sum 小于等于 c，则将当前快递装载到快递车上，更新 sum 和 count。
- 否则，跳出循环。
输出 count，即最多能装载的快递件数。

时间复杂度分析

排序的时间复杂度为 O(NlogN)，遍历数组的时间复杂度为 O(N)。所以总的时间复杂度为 O(NlogN)。

空间复杂度分析

除了输入和输出的空间，额外使用的空间为快递重量数组，空间复杂度为 O(N)。