maxloading.cpp

贪心算法解最大装载问题

template <class Type>
class QNode{
	friend void EnQueue(Queue <QNode <Type>> *> &, Type,
		int, int, Type, QNode <Type> *, QNode <Type> * &, int *, bool);
	friend Type MaxLoading(Type *, Type, int, int *);
	private:
		QNode * parent;
		bool LChild;
		Type weight;
};

template <class Type>
void EnQueue(Queue <QNode <Type> *> & Q, Type wt,
			 int i, int n, Type bestw, QNode <Type> * E,
			 QNode <Type> * &  bestE, int bestx [], bool ch){
	if (i == n){
		if (wt == bestw){
			bestE = E;
			bestx[n] = ch;
		}
		return;
	}
	QNode <Type> * b;
	b = new QNode <Type>;
	b->weight = wt;
	b->parent = E;
	b->LChild = ch;
	Q.Add(b);
}

template <class Type>
Type MaxLoading(Type w[], Type c, int n, int bestx[]){
		Queue <QNode <Type> *> Q;
		Q.Add(0);
		int i = 1;
		Type Ew = 0,
			bestw = 0,
			r = 0;
		for (int j = 2; j <= n; j++)
			r += w[j];
		QNode <Type> * E = 0,
			* bestE;
		while (true){
			Type wt = Ew + w[i];
			if (wt <= c){
				if (wt > bestw) bestw = wt;
				EnQueue(Q, wt, i, n, bestw, E, bestE, bestx, true);
			}
			if (Ew + r > bestw) EnQueue(Q, Ew, i, n,
				bestw, E, bestE, bestx, false);
			Q.Delete(E);
			if (!E){
				if (Q.IsEmpty()) break;
				Q.Add(0);
				Q.Delete(E);
				i++;
				r -= w[i];
			}
			Ew = E->weight;
		}
		for (int j = n - 1; j > 0; j--){
			bestx[j] = bestE->LChild;
			bestE = bestE->parent;
		}
		return bestw;
}