装载问题
template <class Type> HeapNode;
class bbnode {
friend void AddLiveNode(MaxHeap<HeapNode<int>>&, bbnode*, int, bool, int);
friend int MaxLoading(int*, int, int, int*);
friend class AdjacencyGraph;
private:
bbnode *parent;
bool LChild;
};
template <class Type>
class HeapNode {
friend void AddLiveNode(MaxHeap<HeapNode<int>>&, bbnode*, int, bool, int);
friend Type MaxLoading(Type*, Type, int, int*);
public:
operator Type() const { return uweight; };
private:
bbnode *ptr;
Type uweight;
int level;
};
template <class Type>
void AddLiveNode(MaxHeap<HeapNode<Type>> &H, bbnode *E, int wt, bool ch, int lev) {
bbnode *b = new bbnode;
b->parent = E;
b->LChild = ch;
HeapNode<Type> N;
N.uweight = wt;
N.level = lev;
N.ptr = b;
H.Insert(N);
}
template <class Type>
Type MaxLoading(Type w[], Type c, int n, int bestx[]) {
MaxHeap<HeapNode<Type>> H(1000);
Type *r = new Type [n + 1];
r[n] = 0;
for (int j = n - 1; j > 0; j--)
r[j] = r[j + 1] + w[j + 1];
int i = 1;
bbnode *E = 0;
Type Ew = 0;
while (i != n + 1) {
if (Ew + w[i] <= c) {
AddLiveNode(H, E, Ew + w[i] + r[i], true, i + 1);
}
AddLiveNode(H, E, Ew + r[i], false, i + 1);
HeapNode<Type> N;
H.DeleteMax(N);
i = N.level;
E = N.ptr;
Ew = N.uweight - r[i - 1];
}
for (int j = n; j > 0; j--) {
bestx[j] = E->LChild;
E = E->parent;
}
return Ew;
}
最后更新:
2024年1月14日 20:14:02
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42