装载问题

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
回到页面顶部