C++动态规划

　2010-11-16 13:05:18　来源：WEB开发网　　　

核心提示： 11 - 4 + 13＝20，（1）穷举算法： O(n3), O(n2)（2）分治法：将序列a[1:n]从n/2处截成两段：a[1:n/2], a[n/2+1:n]实例三、最大子段和问题表述n个数(可能是负数）组成的序列a1,a2,…an.求该序列子序列的最大值，C++动态规划(4)，也就是例如:

　　　 11 - 4 + 13＝20。

（1）穷举算法： O(n3), O(n2)

（2）分治法：

将序列a[1:n]从n/2处截成两段：a[1:n/2], a[n/2+1:n]

实例三、最大子段和

问题表述

n个数(可能是负数）组成的序列a1,a2,…an.求该序列

子序列的最大值。

也就是

例如: 序列(-2,11,-4,13,-5,-2) ，最大子段和：

　　 11 - 4 + 13＝20。

（1）穷举算法： O(n3), O(n2)

（2）分治法：

将序列a[1:n]从n/2处截成两段：a[1:n/2], a[n/2+1:n]

一共存在三种情况：

a.最大子段和出现在左边一段

b.最大子段和出现在右边一段

c.最大子段和跨越中间的断点

对于前两种情况，只需继续递归调用，而对于第三种情况：

那么S1+S2是第三种情况的最优值。

（3）动态规划法：

定义b[j]：

含义：从元素i开始，到元素j为止的所有的元素构成的子段有多个，这些子段中的子段和最大的那个。

那么：

如果：b[j-1] > 0, 那么b[j] = b[j-1] + a[j]

如果：b[j-1] <= 0,那么b[j] = a[j]

这样，显然，我们要求的最大子段和，是b[j]数组中最大的那个元素。

实现：

/* 主题：最大子段和* 作者：chinazhangjie* 邮箱：chinajiezhang@gmail.com* 开发语言：C++* 开发环境：Microsoft Virsual Studio 2008* 时间: 2010.11.15*/#include <iostream>#include <vector>using namespace std ;class MaxSubSum {public:    MaxSubSum (const vector<int>& intArr)     {        m_vIntArr = intArr ;        m_nLen = m_vIntArr.size () ;    }    // use divide and conquer     int use_DAC ()     {        m_nMssValue = __use_DAC (0, m_nLen - 1) ;        return m_nMssValue ;    }    // use dynamic programming    int use_DP ()     {        int sum = 0 ;        int temp = 0 ;        for (int i = 0; i < m_nLen; ++ i) {            if (temp > 0) {                temp += m_vIntArr[i] ;            }            else {                temp = m_vIntArr[i] ;            }            if (temp > sum) {                sum = temp ;            }        }        m_nMssValue = sum ;        return sum ;    }private:    int __use_DAC (int left, int right)     {        // cout << left << "," << right << endl ;        if (left == right) {            return (m_vIntArr[left] > 0 ? m_vIntArr[left] : 0) ;        }        // 左边区域的最大子段和        int leftSum = __use_DAC (left, (left + right) / 2) ;        // 右边区域的最大子段和        int rightSum = __use_DAC ((left + right) / 2 + 1, right) ;        // 中间区域的最大子段和        int sum1 = 0 ;        int max1 = 0 ;        int sum2 = 0 ;        int max2 = 0 ;        for (int i = (left + right) / 2; i >= left; -- i) {            sum1 += m_vIntArr[i] ;            if (sum1 > max1) {                max1 = sum1 ;            }        }        for (int i = (left + right) / 2 + 1; i <= right; ++ i) {            sum2 += m_vIntArr[i] ;            if (sum2 > max2) {                max2 = sum2 ;            }        }        int max0 = max1 + max2 ;        max0 = (max0 > 0 ? max0 : 0) ;        // cout << max0 << ", " << leftSum << ", " << rightSum << endl ;        return max (max0 , max (leftSum, rightSum)) ;    }private:    vector<int>    m_vIntArr ;    // 整形序列    int            m_nLen ;    // 序列长度    int            m_nMssValue;// 最大子段和} ;int main(){    vector<int> vArr ;    vArr.push_back (-2) ;    vArr.push_back (11) ;    vArr.push_back (-4) ;    vArr.push_back (13) ;    vArr.push_back (-5) ;    vArr.push_back (-2) ;    MaxSubSum mss (vArr) ;    cout << mss.use_DP () << endl ;    return 0 ;}

实例四、多边形游戏

多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符”+”或”*”。所有边依次用整数从1到n编号。

游戏第1步，将一条边删除。

随后n-1步按以下方式操作：

(1)选择一条边E以及由E连接着的2个顶点V1和V2；