用c写一段贪心算法代码【问题描述】有n个集装箱要装上一艘载重量为W的轮船,其中集装箱i(1≤i≤n)的重量为wi。不考虑集装箱的体积限制,现要选出尽可能多的集装箱装上轮船,使它们的重量之和不超过W。 【测试用例】n=5,各集装箱重量{5,2,6,4,3};W=10;
时间: 2024-06-05 10:06:08 浏览: 13
#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;
}