Hrvatski matematički elektronski časopis math.e

http://www.math.hr/~mathe/

Heuristički algoritmi za 0-1 problem naprtnjače

Anamari Nakić

Pseudokod tabu algoritma za 0-1 problem naprtnjače



array tabu_algorithm (int cmax, int L, array w, array p, int n, real M) {

    set N;
    int start, c, i;
    array Xbest, X, TabuList;

    c = 1;
    X = [x0, ..., xn-1];        // x[i] = 0 ili x[i] = 1,
                                    // neko slucajno dopustivo rjesenje
    CurW = 0;
    for  i = 0 to  n-1
        CurW = CurW + X[i]*w[i];
    Xbest = X;
    while( c <= cmax) {
            N = {0, ..., n-1};
            start = max{0, c-L};
            for j = start to c-1
                    N = N \ {TabuList[j]};
            for each i element_of  N {
                    if (X[i] == 0) && (CurW + w[i] > M)
                        N = N \ {i};
            }
            if ( empty(N) )
                    exit;
            find i element_of N so that  (-1)^X[i]*p[i]/w[i] is maximum;
            TabuList[c] = i:
            X[i] = 1 - X[i];
            if ( X[i] == 1 )
                    CurW = CurW + w[i];
            else
                    CurW = CurW - w[i];
            if ( P(X) > P(Xbest) )
                    Xbest = X;
            c = c + 1;
    }
    return (Xbest);
}