贪心算法最优装载问题C语言
时间: 2023-07-11 15:50:44 浏览: 87
贪心算法最优装载问题的 C 语言实现如下:
```c
#include <stdio.h>
#define MAX_N 100 // 最大集装箱数量
int n; // 集装箱数量
int w[MAX_N]; // 集装箱重量
int c; // 轮船的载重量
// 贪心算法:最优装载问题
int best_fit() {
int ans = 0; // 轮船数量
int b[MAX_N] = {0}; // 标记集装箱是否已装载
for (int i = 0; i < n; i++) {
int k = -1; // 最优选择
for (int j = 0; j < ans; j++) {
if (b[j] == 0 && w[i] <= c - b[j]) {
if (k == -1 || b[k] < b[j]) {
k = j;
}
}
}
if (k == -1) {
b[ans++] = w[i];
} else {
b[k] += w[i];
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &c);
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
printf("%d\n", best_fit());
return 0;
}
```
该算法的时间复杂度为 $O(n^2)$。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)