开发学院软件开发C++ C++动态规划 阅读

C++动态规划

 2010-11-16 13:05:18 来源:WEB开发网   
核心提示:(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2,将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点,C++动态规划(5),最后,所有边都被删除,主链的最大值和最小值可由子链的最大值和最小值得到,实现:/* 主题:多边形游戏* 作者:chinazhangjie* 邮箱:chinajiezhan
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。
问题: 对于给定的多边形,计算最高得分。
最优子结构性质
按照顺时针顺序,多边形和顶点的顺序可以写成:
   op[1], v[1], op[2], v[2], …, op[n], v[n]
在所给多边形中,从顶点i(1 <= i <= n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j) 可表示为
v[i], op[i+1], v[i+1],…, op[i+j-1], v[i+j-1]
如果这条链在op[i + s]处进行最后一次合并运算(1 <= s <= j-1),则可在op[i+s]处将链分割为2个子链:
从i开始长度为s的链: p(i,s)
从i + s开始,长度为j - s的链:p(i + s,j-s)。
设:
m1是对子链p(i,s)的任意一种合并方式得到的值,而a和b分别是在所有可能的合并中得到的最小值和最大值。
m2是p(i+s,j-s)的任意一种合并方式得到的值,而c和d分别是在所有可能的合并中得到的最小值和最大值。
依此定义有a <= m1 <= b,c <= m2 <= d
(1)当op[i+s] = ‘+’时,显然有a + c <= m <= b + d
(2)当op[i+s] = ’*’时,有
min {ac,ad,bc,bd} <= m <= max {ac,ad,bc,bd}
换句话说,主链的最大值和最小值可由子链的最大值和最小值得到。
实现:
/* 主题:多边形游戏* 作者:chinazhangjie* 邮箱:chinajiezhang@gmail.com* 开发语言:C++* 开发环境:Vicrosoft Visual Studio* 时间: 2010.11.15*/#include <iostream>#include <vector>using namespace std ;struct SegInfo{public:    SegInfo ()         : m_nMaxValue (0), m_nMinValue(0)     {}    SegInfo (int maxValue, int minValue)         : m_nMaxValue (maxValue), m_nMinValue (minValue)     {}public:    int m_nMaxValue ;    int m_nMinValue ;} ;class PolyGame {public:    PolyGame (const vector<char>& op, const vector<int>& vertex)     {        m_vcOp = op ;        m_vnVertex = vertex ;        m_nCount = m_vcOp.size () ;        m_vSeg.resize (m_nCount) ;        for (int i = 0; i < m_nCount; ++ i) {            m_vSeg[i].resize (m_nCount) ;        }    }        int beginCalulate ()     {        // 初始边界        for (int i = 1; i < m_nCount; ++ i) {            m_vSeg[i][1].m_nMaxValue = m_vnVertex[i] ;            m_vSeg[i][1].m_nMinValue = m_vnVertex[i] ;        }        // i: 起点        // j: 长度        // s: 子切分位置        for (int j = 2; j < m_nCount ; ++ j) {            for (int i = 1; i < m_nCount; ++ i) {                for (int s = 1; s < j; ++ s) {                    SegInfo si = __calMinAndMax(i, s, j) ;                    if (m_vSeg[i][j].m_nMinValue > si.m_nMinValue) {                        m_vSeg[i][j].m_nMinValue = si.m_nMinValue ;                    }                     if (m_vSeg[i][j].m_nMaxValue < si.m_nMaxValue) {                        m_vSeg[i][j].m_nMaxValue = si.m_nMaxValue ;                    }                }            }        }        // 找到最大值        int temp = m_vSeg[1][m_nCount - 1].m_nMaxValue ;        for (int i = 2; i < m_nCount; ++ i) {            if (temp < m_vSeg[i][m_nCount - 1].m_nMaxValue) {                temp = m_vSeg[i][m_nCount - 1].m_nMaxValue ;            }        }        m_nResult = temp ;        return m_nResult ;    }private:    // 从i开始,长度为j,s为切分位置    SegInfo __calMinAndMax (int i, int s, int j)     {        int minL = 0 ;        int maxL = 0 ;        int minR = 0 ;        int maxR = 0 ;        minL = m_vSeg[i][s].m_nMinValue ;        maxL = m_vSeg[i][s].m_nMaxValue ;        int r = (i + s - 1) % (m_nCount - 1) + 1 ;        minR = m_vSeg[r][j - s].m_nMinValue ;        maxR = m_vSeg[r][j - s].m_nMaxValue ;        SegInfo si ;        // 处理加法        if (m_vcOp[r] == '+') {            si.m_nMinValue = minL + minR ;            si.m_nMaxValue = maxL + maxR ;        }        else {    // 处理乘法            vector<int> mm ;            mm.push_back (minL * minR) ;            mm.push_back (minL * maxR) ;            mm.push_back (maxL * minR) ;            mm.push_back (maxL * maxR) ;            int min = 0 ;            int max = 0 ;            for (vector<int>::iterator ite = mm.begin();                 ite != mm.end() ; ++ ite) {                if (*ite < min) {                    min = *ite ;                }                if (*ite > max) {                    max = *ite ;                }             }            si.m_nMinValue = min ;            si.m_nMaxValue = max ;        }        return si ;     }private :    vector<char>    m_vcOp ;    // 运算符(下标从1开始)    vector<int>        m_vnVertex ;// 顶点值(下标从1开始)    int                m_nCount ;    // 边的个数    int                m_nResult ;    // 结果    vector<vector<SegInfo> > m_vSeg ;// 合并后的信息} ;int main(){    const int cnCount = 5 ;    vector<char> op (cnCount + 1);    vector<int>     vertex (cnCount + 1);    op[1] = '+' ;    op[2] = '*' ;    op[3] = '+' ;    op[4] = '*' ;    op[5] = '*' ;    vertex[1] = 10 ;    vertex[2] = -8 ;    vertex[3] = 3;    vertex[4] = -2 ;    vertex[5] = -1 ;    PolyGame pg (op, vertex) ;    cout << pg.beginCalulate () << endl ;}

上一页  1 2 3 4 5 

Tags:动态 规划

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接