C语言贪心算法求解3.最优装载问题 【问题描述】有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要选出尽可能多的集装箱装上轮船，使它们的重量之和不超过W。

【算法描述】
贪心算法的思想是每一步都选择当前状态下最优的解，从而达到全局最优的目的。对于本问题，可以按照集装箱的重量从大到小排序，然后依次将重量最大的集装箱装上轮船，直到轮船的载重量达到上限W或者所有集装箱都被装上。

【算法实现】
以下是用C语言实现最优装载问题的贪心算法代码。

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000

int cmp(const void *a, const void *b) { // 从大到小排序
    return *(int *)b - *(int *)a;
}

int main() {
    int n, W;
    int w[MAX_N];

    // 输入数据
    scanf("%d%d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }

    // 按重量从大到小排序
    qsort(w, n, sizeof(int), cmp);

    // 贪心选择
    int cnt = 0;
    for (int i = 0; i < n && W > 0; i++) {
        if (w[i] <= W) {
            cnt++;
            W -= w[i];
        }
    }

    // 输出结果
    printf("%d\n", cnt);

    return 0;
}

【算法分析】
时间复杂度：排序的时间复杂度为O(nlogn)，贪心选择的时间复杂度为O(n)，所以总的时间复杂度为O(nlogn)。
空间复杂度：只需要使用常数级别的额外空间，所以空间复杂度为O(1)。