Listing 1: Dynamic programming functions

void SHM_Math::Select(int& N, double* D, double* X, double* C, double K)
{ // expects array indices in 1,n range, elements 1 and n are virtual
  // outputs arrays in 0,n-1 range.                               
        double ZMAX = 999999999;
    if (N == 2 || K <= 0) {
        N = 0;
        return;
    }

    double* F = new double[N + 1];
    int* H = new int[N + 1];
    int* P = new int[N + 1];

    D[1] = ZMAX; X[1] = ZMAX; C[1] = 0;
    D[N] = ZMAX; X[N] = ZMAX; C[N] = 0;
    
    F[1] = 0;
    for (int I = 2; I <= N; ++I) {
        double FMIN = ZMAX; int JMIN = 0;
        double T = 0;

        for (int J = I - 1; J >= 1; --J) {

            if (J != I - 1) T += K * C[J + 1];
            if (T > FMIN) break;

            if (Contradict(D[I], X[I], D[J], X[J])) continue;

            double G;
            if (I == 1 || I == N || J == 1)
                G = T + F[J];
            else
                G = F[J] + Tension(D[I], X[I], D[J], X[J]) + T;

            if (G < FMIN) {
                FMIN = G;
                JMIN = J;
            }
        }
        F[I] = FMIN;
        H[I] = JMIN;
    }

    int MM = 0;
    int M = N;

    while (1) {    
        M = H[M];
        if (M == 1) break;
        ++MM;
        P[MM] = M;
    }
    for (M = 1; M <= MM / 2; ++M) {
        int SAVE = P[M];
        P[M] = P[MM - M + 1];
        P[MM - M + 1] = SAVE;
    }

    for (M = 1; M <= MM; ++M) {
        D[M] = D[P[M]];
        X[M] = X[P[M]];
        C[M] = C[P[M]];
    }
    N = MM;           
             
    // change to 0,N-1 range
    for (I = 1; I <= N; ++I) {
        D[I - 1] = D[I];  
        X[I - 1] = X[I];
        C[I - 1] = C[I]; 
    }
    delete F;
    delete H;
    delete P;     
}
---------------------------------------------------------------------
void SHM_Math::Select(int N, OptimizationObject** objects, double K)
{ // expects array indices in 1,n range, elements 1 and n are virtual
  // does not renumber arrays, instead sets the 'selected' member

    if (N == 2 || K <= 0) {
        return;
    }

    for (int i = 1; i <= N; ++i) 
        objects[i]->selected = 0;

    double* F = new double[N + 1];
    int* H = new int[N + 1];
    int* P = new int[N + 1];

    objects[1]->selected = -1;
    objects[N]->selected = -1;
    
    F[1] = 0;
    for (int I = 2; I <= N; ++I) {
        double FMIN = ZMAX; int JMIN = 0;
        double T = 0;

        for (int J = I - 1; J >= 1; --J) {

            if (J != I - 1) T += K * objects[J + 1]->grade;
            if (T > FMIN) break;

            if (objects[I]->Contradict(*objects[J])) continue;

            double G;
            if (I == 1 || I == N || J == 1)
                G = T + F[J];
            else
                G = F[J] + objects[I]->Tension(*objects[J]) + T;
            if (G < FMIN) {
                FMIN = G;
                JMIN = J;
            }
        }

        F[I] = FMIN;
        H[I] = JMIN;
    }

    int MM = 0;
    int M = N;

    while (1) {    
        M = H[M];
        if (M == 1) break;
        ++MM;
        P[MM] = M;
    }
    for (M = 1; M <= MM / 2; ++M) {
        int SAVE = P[M];
        P[M] = P[MM - M + 1];
        P[MM - M + 1] = SAVE;
    }

    for (M = 1; M <= MM; ++M) 
        objects[P[M]]->selected = 1;
             
    delete F;
    delete H;
    delete P;     
}
//And this is the declaration of optimization object class:

class OptimizationObject 
{
public:
    int selected;
    double grade;
public:
    OptimizationObject();
    virtual ~OptimizationObject();
    virtual double Tension(OptimizationObject& other) = 0;
    virtual int Contradict(OptimizationObject& other) = 0;
};