用c写一段贪心算法代码【问题描述】有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要选出尽可能多的集装箱装上轮船，使它们的重量之和不超过W。 【测试用例】n=5,各集装箱重量{5,2,6,4,3};W=10;

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

int cmp(const void *a, const void *b) {
return *(int*)b - *(int*)a; // 降序排序
}

int main() {
int n, W;
scanf("%d%d", &n, &W);
int *weights = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &weights[i]);
}
qsort(weights, n, sizeof(int), cmp); // 排序
int count = 0, sum = 0;
for (int i = 0; i < n; i++) {
if (sum + weights[i] <= W) { // 能装下
sum += weights[i];
count++;
} else { // 装不下
break;
}
}
printf("%d\n", count);
free(weights);
return 0;
}

相关问题

最优装载问题: 有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i(1sisn)的重量为wi。不考虑集装箱的体积限制，现要选出尽可能多的集装箱装上轮船，便它们的重量之和不超过W。可以采用贪心策略求解最优装载问题。各集装箱重量wl]={0,5,2,6,4,3}; =5,W=10: 最优装载的集装箱是 ()。

根据题目描述，这是一个最优装载问题，可以采用贪心策略求解。

一种可行的贪心策略是选择重量最小的集装箱，依次放入轮船中，直到无法再放入为止。

按照这个策略，我们可以先将集装箱按重量从小到大排序，然后依次将集装箱放入轮船中，直到轮船载重达到上限或者所有集装箱都已放入。

具体过程如下：

1. 将集装箱按重量从小到大排序，得到排序后的重量数组：{0, 2, 3, 4, 5, 6}。

2. 初始化轮船当前载重为0，选中集装箱的下标数组为空。

3. 从重量数组的第一个元素开始，依次遍历每个集装箱：

a. 如果当前集装箱的重量加上轮船当前载重小于等于轮船的最大载重W，那么将该集装箱放入轮船中，更新轮船当前载重和选中集装箱的下标数组。

b. 如果当前集装箱的重量加上轮船当前载重大于轮船的最大载重W，那么跳出循环，结束遍历。

4. 输出选中集装箱的下标数组，即为最优装载的集装箱。

按照上述步骤，对于重量数组{0, 5, 2, 6, 4, 3}和最大载重W=10，得到最优装载的集装箱为(1, 2, 5)，对应的重量为{5, 2, 3}，重量之和为10，满足题目要求。

有n个集装箱要装上一搜载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi，不考虑集装箱的体积限制，现在要尽可能多的集装箱装上轮船，使得他们的重量之和不超过W，使用贪心法，给出代码

贪心算法在这种情况下可以采用优先选择重量最大的集装箱并尽量填满轮船，直到轮船无法承载更多为止。这种策略称为最大单位重量装载（Maximum Weight First）。以下是使用Python实现的简单贪心算法：

def max_weight_on_boat(n, W, weights):
    # 初始化结果变量和容器列表
    result = []
    remaining_weight = W

    # 按照权重降序排序
    sorted_weights = sorted(range(n), key=lambda i: weights[i], reverse=True)

    for i in sorted_weights:
        if remaining_weight >= weights[i]:
            result.append(i)
            remaining_weight -= weights[i]

    return result, remaining_weight  # 返回装上的集装箱索引和剩余载重量


# 示例
n = 5
weights = [20, 40, 60, 70, 80]
W = 150
result, remaining_weight = max_weight_on_boat(n, W, weights)
print("装上轮船的集装箱索引:", result)
print("剩余载重量:", remaining_weight)