48 lines
1.6 KiB
C
48 lines
1.6 KiB
C
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
typedef struct { float weight; int index;} Element;
|
||
int compare(const void *a, const void *b) {
|
||
const Element *elemA = (const Element *)a;
|
||
const Element *elemB = (const Element *)b;
|
||
return (elemA->weight > elemB->weight) - (elemA->weight < elemB->weight);
|
||
}
|
||
// 最优装载函数
|
||
float loading(float capacity, float weights[], int count, int x[]) {
|
||
Element *elements = malloc(count * sizeof(Element));
|
||
for (int i = 0; i < count; i++) { // 初始化元素
|
||
elements[i].weight = weights[i];
|
||
elements[i].index = i;
|
||
}
|
||
qsort(elements, count, sizeof(Element), compare); // 排序元素
|
||
// 初始化装载情况
|
||
for (int i = 0; i < count; i++) { x[i] = 0; }
|
||
float totalWeight = 0;
|
||
// 贪心选择
|
||
for (int i = 0; i < count && elements[i].weight <= capacity; i++) {
|
||
totalWeight += elements[i].weight;
|
||
capacity -= elements[i].weight;
|
||
x[elements[i].index] = 1; // 标记被装载的集装箱
|
||
}
|
||
free(elements); // 释放动态分配的内存
|
||
return totalWeight;
|
||
}
|
||
int main() {
|
||
float weights[] = {20, 30, 26, 15, 30, 40, 35,50,25};
|
||
float capacity = 100;
|
||
int count = sizeof(weights) / sizeof(weights[0]);
|
||
int *x = malloc(count * sizeof(int));
|
||
|
||
float optimalWeight = loading(capacity, weights, count, x);
|
||
|
||
printf("最优得到装载重量为：%.2f\n", optimalWeight);
|
||
printf("被装载的集装箱序号为(下标从0开始)：");
|
||
|
||
for (int i = 0; i < count; i++) {
|
||
if (x[i] == 1) {
|
||
printf("%d ", i);
|
||
}
|
||
}
|
||
free(x); // 释放动态分配的内存
|
||
return 0;
|
||
}
|