c语言实现最优装载的贪心算法

最优装载问题是指在给定容量的货车和若干个货物的情况下，如何将货车尽可能装满货物，使得装载的货物总重量最大。这是一个经典的贪心算法问题。

算法思路：

1. 将所有货物按照单位重量的价值从大到小排序。
2. 从价值最高的货物开始，逐个将货物装入货车，直到货车装满或者所有货物都已经装入。
3. 如果当前货物无法完全装入货车，则将其部分装入。

C语言实现：

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

#define MAX_N 100 // 最大货物数量

// 货物结构体
typedef struct {
int weight; // 重量
int value; // 价值
} Goods;

// 按照单位重量价值从大到小排序
int cmp(const void* a, const void* b) {
Goods* ga = (Goods*)a;
Goods* gb = (Goods*)b;
double va = 1.0 * ga->value / ga->weight;
double vb = 1.0 * gb->value / gb->weight;
if (va < vb) return 1;
if (va > vb) return -1;
return 0;
}

// 最优装载算法
double loading(int n, int c, Goods* goods) {
qsort(goods, n, sizeof(Goods), cmp); // 排序
double ans = 0;
int i;
for (i = 0; i < n; i++) {
if (goods[i].weight <= c) {
ans += goods[i].value;
c -= goods[i].weight;
} else {
ans += 1.0 * goods[i].value * c / goods[i].weight;
break;
}
}
return ans;
}

// 测试代码
int main() {
int n, c, i;
Goods goods[MAX_N];
printf("请输入货物数量和货车容量：");
scanf("%d%d", &n, &c);
printf("请输入每个货物的重量和价值：\n");
for (i = 0; i < n; i++) {
scanf("%d%d", &goods[i].weight, &goods[i].value);
}
printf("最优装载的总价值为：%.2f\n", loading(n, c, goods));
return 0;
}