12-1.c

来自「数据结构经典算法一书源代码和习题解答实现代码。」· C语言 代码 · 共 30 行

#include "stdio.h"
#include <malloc.h>
#define Max_Pack 100
typedef int TypeData;
void ContainerLoading(int x[], TypeData w[], TypeData c, int n)
{// 货箱装船问题的贪婪算法,x[i]=1当且仅当货箱i被装载,0<=i<n
// c是船的容量, w 是货箱的重量。对重量按间接寻址方式排序
// t 是间接寻址表
	int *t =(int*)malloc(sizeof(n+1));
	int i;
	IndirectSort(w, t, n);
	// 此时, w[t[i]] <= w[t[i+1]], 1<=i<n
	// 初始化x
	for (i = 1; i <= n; i++)
		x[i] = 0;
	// 按重量次序选择物品
	for (i = 1; i <= n && w[t[i]] <= c; i++) {
		x[t[i]] = 1;
		c -= w[t[i]];
	} // 剩余容量
	free(t);
}
void main(void)
{
	int x[Max_Pack];
	TypeData w[Max_Pack],c;
	//初始化x,w,c;
	ContainerLoading(x,w,c,Max_Pack);
}