12-11.c

数据结构用C语言实现

#include "stdio.h"
#define M 10
typedef int DataType;
typedef struct {
	int n; // 货箱数目
	DataType *w, // 货箱重量数组
	c, // 第一艘船的容量
	cw, // 当前装载的重量
	bestw; // 目前最优装载的重量
}Loading ;
void maxLoading(Loading *x,int i)
{// 从第i 层节点搜索
	if (i>x->n) {// 位于叶节点
		if (x->cw >x->bestw) 
			x->bestw = x->cw;
		return ; 
	}
	// 检查子树
	if (x->cw + x->w[i] <= x->c) 
	{// 尝试x[i] = 1
		x->cw += x->w[i];
		maxLoading(x,i + 1 ) ;
		x->cw -= x->w[i];
	}
	maxLoading(x,i+1);// 尝试x[i] = 0
}
DataType MaxLoading(DataType w[], DataType c, int n)
{// 返回最优装载的重量
	Loading X;
	// 初始化X
	X.w = w;
	X.c = c;
	X.n = n;
	X.bestw = 0;
	X.cw = 0;
	// 计算最优装载的重量
	maxLoading(&X,1) ;
	return X.bestw;
}
void main()
{
	DataType w[M],c;
	//初始化w[M],c;
	MaxLoading(w,c,M);
}