最优装载问题贪心算法c语言
时间: 2023-12-02 10:42:38 浏览: 70
以下是最优装载问题的贪心算法C语言实现:
```c
#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
int n, C, w[MAXN];
int main() {
int i, num = 0, sum = 0;
printf("请分别输入物体的数量和装载总重量(用逗号隔开):");
scanf("%d,%d", &n, &C);
for (i = 0; i < n; i++) {
printf("请依次输入第%d个物体的重量:", i + 1);
scanf("%d", &w[i]);
}
sort(w, w + n); //调用sort函数将重量从小到大排序
for (i = 0; i < n; i++) {
if (sum + w[i] <= C) { //如果能装载第i件物品,装载之
sum += w[i];
num++;
}
}
printf("最多可以装载%d个物体", num);
return 0;
}
```
相关问题
最优装载贪心算法c语言实现
以下是最优装载贪心算法的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
int w[MAX_N]; // 集装箱重量
int n; // 集装箱数量
int c; // 轮船载重量
// 比较函数,用于快速排序
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
// 贪心算法求解最优装载问题
int solve() {
int ans = 0; // 装载的集装箱数量
int sum = 0; // 当前已装载的集装箱重量
// 将集装箱按重量从小到大排序
qsort(w, n, sizeof(int), cmp);
// 从轻到重依次装载集装箱
for (int i = 0; i < n; i++) {
if (sum + w[i] <= c) { // 如果当前集装箱可以装载
ans++;
sum += w[i];
} else { // 如果当前集装箱无法装载
break;
}
}
return ans;
}
int main() {
// 读入数据
scanf("%d%d", &n, &c);
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
// 求解并输出结果
printf("%d\n", solve());
return 0;
}
```
c语言实现最优装载的贪心算法
最优装载问题指的是给定若干个物品和一个容量为C的背包,每个物品有自己的重量和价值,在保证不超过背包容量的前提下,选择若干个物品放入背包,使得背包中物品的总价值最大。以下是C语言实现最优装载的贪心算法的代码:
```c
#include <stdio.h>
#define MAX_N 1000 // 最大物品数
#define MAX_C 10000 // 最大背包容量
struct Item {
int weight; // 物品重量
int value; // 物品价值
} items[MAX_N];
int cmp(const void *a, const void *b) {
struct Item *ia = (struct Item *) a;
struct Item *ib = (struct Item *) b;
double va = (double) ia->value / ia->weight;
double vb = (double) ib->value / ib->weight;
return vb > va ? 1 : vb < va ? -1 : 0;
}
int main() {
int n, c;
scanf("%d%d", &n, &c);
for (int i = 0; i < n; i++) {
scanf("%d%d", &items[i].weight, &items[i].value);
}
qsort(items, n, sizeof(struct Item), cmp);
int ans = 0;
for (int i = 0; i < n && c > 0; i++) {
int take = c < items[i].weight ? c : items[i].weight;
ans += take * (double) items[i].value / items[i].weight;
c -= take;
}
printf("%d\n", ans);
return 0;
}
```
算法思路:
1. 按照每个物品的单位价值(即价值除以重量)从大到小排序;
2. 依次将单位价值最高的物品放入背包中,直到背包放满为止;
3. 计算背包中物品的总价值。
时间复杂度:O(nlogn),主要是排序的时间复杂度。