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

【输入格式】
第一行输入一个正整数T，表示数据组数。
每组数据第一行输入两个正整数n和W，表示集装箱数量和轮船载重量。
接下来一行输入n个正整数，表示每个集装箱的重量。

【输出格式】
对于每组数据，输出一行一个整数，表示最多可以装载的集装箱数量。

【样例输入】
2
6 100
50 30 40 10 20 30
3 50
10 20 30

【样例输出】
4
3

【思路分析】
1. 对集装箱的重量进行排序，从小到大。
2. 从最轻的集装箱开始，尽可能多地往轮船上装载，直到无法再装载。
3. 统计已经装载的集装箱数量并输出。

【注意事项】
1. 本题需要对输入数据进行多组处理，要求在处理完一组数据后清空相关变量，避免对下一组数据造成影响。
2. 载重量不超过0，或集装箱数量为0时，输出0。

相关问题

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)。

贪心算法最优装载问题c语言

贪心算法最优装载问题是指有一批集装箱需要装载到船上，每个集装箱的重量不同且船的载重量有限，需要确定如何装载才能使船的装载重量最大。贪心算法最优装载问题的解决思路是每次选择当前剩余载重量中可以装载的最重集装箱装载到船上，直到无法再装载为止。

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

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

int cmp(const void *a, const void *b) {  // qsort排序需要使用的比较函数
    return *(int *)b - *(int *)a;
}

int main() {
    int n, c;  // 集装箱数量n和船的载重量c
    scanf("%d%d", &n, &c);
    int w[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    qsort(w, n, sizeof(int), cmp);  // 将集装箱按重量从大到小排序
    int ans = 0, sum = 0;
    for(int i = 0; i < n; i++) {
        if(sum + w[i] <= c) {  // 如果当前集装箱可以装载到船上
            ans++;  // 船上集装箱数量+1
            sum += w[i];  // 船上已装载集装箱重量增加
        } else {
            break;
        }
    }
    printf("%d\n", ans);  // 输出最多可装载集装箱数量
    return 0;
}