贪心算法最优装载问题c语言
时间: 2024-05-24 11:09:10 浏览: 245
贪心算法最优装载问题是指有一批集装箱需要装载到船上,每个集装箱的重量不同且船的载重量有限,需要确定如何装载才能使船的装载重量最大。贪心算法最优装载问题的解决思路是每次选择当前剩余载重量中可以装载的最重集装箱装载到船上,直到无法再装载为止。
以下是贪心算法最优装载问题的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;
}
```
阅读全文