Dynamic Programming
by Mark A. Pumar

Listing One
// DpSolution.hpp. This class encapsulates the dynamic programming solution. 
// It uses the abstract class DpObject which contains the interface to the 
// problem and uses the functions in this interface to calculate the solution 
// to the problem. The class contains the following public functions:

#ifndef _DP_SOLUTION
#define _DP_SOLUTION

#include <list>
#include <vector>
#include <iostream>

#include "DpObject.hpp"


class DpSolution
{
   public:
      DpSolution(const list<DpObject *> &dp, int N, bool sortList = true);
     ~DpSolution(void);
      list<DpObject *> solve(void);
      int stages(void) const;
      int stages(int stageNum) const;
      DpObject * stage(int stageNum,int objectNum) const;
      friend ostream& operator<<( ostream& os, const DpSolution& dps );
   private:
      typedef vector<DpObject *> Strategy;
      typedef vector<Strategy> Stage;
      Stage m_stage;  // solution strategies
};
#endif

Listing Two
// DpObject.hpp. Abstract class definition for dynamic solution object. This 
// class defines the interface between the problem and the DpSolution class 
// which is used to determine the solution. Inheriting class are required to 
// define the following member functions:

#ifndef _DPOBJECT_
#define _DPOBJECT_

#include <string>

using namespace std;
class DpObject
{
   public:
     // constructors/destructor
     DpObject(void);
     DpObject(const DpObject &tp);
     virtual ~DpObject(void);
     // member functions
     string id(void) const;
     int partner(void) const;
     double cost(void) const;
     DpObject *clone(void) const;
     // cirtual functions
     virtual void setCost(double cost);
     virtual void setPartner(int index, int stage);
     // Pure virtual functions
     virtual bool operator>(const DpObject & dp) const = 0;
     virtual bool operator<(const DpObject & dp) const = 0;
     virtual void setPartner(int index, int stage, const DpObject *dp) = 0;
     virtual double evalCost(const DpObject *dp) const = 0;
     virtual double evalInitialCost(void) const = 0;
     virtual double evalFinalCost(void) const = 0;
     // friend functions
     friend ostream& operator<<( ostream& os, const DpObject& dp );
   protected:

      string m_id;          // object identifier
      int    m_partner;     // object partner
      double m_cost;        // object cost
   private:
      virtual DpObject *cloneDpObject(void) const = 0;
      virtual void print(ostream& os) const = 0;
};
// comparison function used for sorting
inline bool DpObjectPtrLessThan(DpObject *dp1, DpObject *dp2) 
{
   return(*dp1 < *dp2);
}
#endif

Listing Three
// Constructor
// Inputs:
// const list<DpObject *> &dp - object containing the problem definition
// int                    N   - number of objects desired in solution
// ABSTRACT: Initialize solution class for finding the problem solution. 

DpSolution::DpSolution(const list<DpObject *> &dp, int N, bool sortList) 
{
   // copy and sort input objects
   Strategy p;
   for(list<DpObject *>::const_iterator iter = dp.begin(); 
                                               iter != dp.end(); ++iter)
   {
      p.push_back((*iter)->clone());
   }
   if(sortList) sort(p.begin(),p.end(),DpObjectPtrLessThan);
   // create solution stages
   m_stage.resize(N);
   for(int i = 0; i < m_stage.size(); ++i)
   {
     m_stage[i].resize(dp.size());
     // store tracking passes
     int j = 0;
     for(Strategy::iterator iter = p.begin(); 
                           (iter != p.end()) && (j < dp.size()); ++iter)
     {
        m_stage[i][j] = (*iter)->clone();
        ++j;
     }
   }
   // delete sorted list
   for(Strategy::iterator piter = p.begin(); piter != p.end(); ++piter)
   {
      delete *piter;
   }
}

Listing Four
// Function: solve
// Inputs: None

// Returns: list<DpObject *> - list of objects in solution
// ABSTRACT: Calculate and return list of object that from optimal solution 

list<DpObject *> DpSolution::solve(void) 
{  // check that solution is feasable
   if(m_stage[0].size() <= m_stage.size())
   {  // no solution, return inputs
      list<DpObject *> ans;
      for(int j = 0; j < m_stage[0].size(); ++j)
      { ans.push_front(m_stage[0][j]->clone());}
      return(ans);
   }
   // compute stage 1 (initial) strategy/cost
   for(int j = 0; j < m_stage[0].size(); ++j)
   {
      m_stage[0][j]->setCost(m_stage[0][j]->evalInitialCost());
   }
   // compute stage 2 to N-1 strategies/costs
   for(int i = 1; i < m_stage.size(); ++i)
   {
     for(int j = 1; j < m_stage[i].size(); ++j)
     {
        double cmin = m_stage[i][j]->evalCost(m_stage[i-1][0]) +
                                              m_stage[i-1][0]->cost();
        int partner = 0;
        for(int k = 1; k < j; ++k)
        {
           double c = m_stage[i][j]->evalCost(m_stage[i-1][k])  + 
                                              m_stage[i-1][k]->cost();
           if(c < cmin) { cmin = c; partner = k; }
        }
        m_stage[i][j]->setCost(cmin);
        m_stage[i][j]->setPartner(partner, i-1, m_stage[i-1][partner]);
     }
   }
   // compute final stage N strategy/cost
   double cmin = m_stage[m_stage.size()-1][0]->cost() +
                         m_stage[m_stage.size()-1][0]->evalFinalCost();
   int    imin = 0;
   for(int k = 1; k < m_stage[m_stage.size()-1].size(); ++k)
   {
     m_stage[m_stage.size()-1][k]->
                       setCost(m_stage[m_stage.size()-1][k]->cost() +
                       m_stage[m_stage.size()-1][k]->evalFinalCost());
     if(m_stage[m_stage.size()-1][k]->cost() < cmin)
     {
        imin = k;
        cmin = m_stage[m_stage.size()-1][k]->cost();
     }
   }
   // extract solution
   list<DpObject *> ans;
   int is = m_stage.size()-1;
   while((imin >= 0) && (is >= 0))
   {

      DpObject *tp = m_stage[0][imin]->clone();
      tp->setCost(m_stage[is][imin]->cost());
      tp->setPartner(m_stage[is][imin]->partner(),imin);
      ans.push_front(tp);
      imin = m_stage[is][imin]->partner();
      --is;
   }
   return(ans);
}






4


