C++动态规划
2010-11-16 13:05:18 来源：WEB开发网核心提示：那么S1+S2是第三种情况的最优值，（3）动态规划法：定义b[j]：含义：从元素i开始，C++动态规划(7)，到元素j为止的所有的元素构成的子段有多个，这些子段中的子段和最大的那个，那么：如果：b[j-1] > 0, 那么b[j] = b[j-1] + a[j]如果：b[j-1] <= 0,那么b[j] =
那么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 ;}
中查找“C++动态规划”更多相关内容
中查找“C++动态规划”更多相关内容更多精彩
赞助商链接
