Skip to content

Commit 36af0a8

Browse files
xubenhaoxubenhao
committed
动态规划经典问题
动态规划经典问题
1 parent 8a93789 commit 36af0a8

File tree

4 files changed

+301
-0
lines changed

4 files changed

+301
-0
lines changed

‎Design/DynamicPlanning/MaxProfit.cpp‎

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
#define ALGORITHMLIB __declspec(dllexport)
2+
#include "MaxProfit.h"
3+
4+
// 算法输入：
5+
// nLength_ 总的长度
6+
// pPriceTable_ 一个数组。给出每个长度len和此长度对应的价格price
7+
// 输入限制：
8+
// 对于价格数组中，任意一组，满足 len > 0, price >= 0
9+
// 划分必须按整数长度进行
10+
// 算法目标：
11+
// 求取给定输入nLength_下，
12+
// 一个对nLength_的可取得最大价格的划分方案，及该划分方案下的价格
13+
double CalculateMaxProfit1(
14+
int nLength_,
15+
const double* pPriceTable_,
16+
int nNum_)
17+
{
18+
if (nLength_ == 0)
19+
{
20+
return 0;
21+
}
22+
23+
if (nLength_ == 1)
24+
{
25+
return pPriceTable_[1];
26+
}
27+
28+
double _nMaxProfit = 0;
29+
for (int _i = 1; _i <= nLength_; _i++)
30+
{
31+
double _nTempMax = pPriceTable_[_i] + CalculateMaxProfit1(nLength_ - _i, pPriceTable_, nNum_);
32+
if (_nTempMax > _nMaxProfit)
33+
{
34+
_nMaxProfit = _nTempMax;
35+
}
36+
}
37+
38+
return _nMaxProfit;
39+
}
40+
41+
// 算法输入：
42+
// nLength_ 总的长度
43+
// pPriceTable_ 一个数组。给出每个长度len和此长度对应的价格price
44+
// pMaxProfitTable_ 一个数组。存储已经知道的len和此len下最优划分方案的价格。
45+
// 输入限制：
46+
// 对于价格数组中，任意一组，满足 len > 0, price >= 0
47+
// 划分必须按整数长度进行
48+
// 算法目标：
49+
// 求取给定输入nLength_下，一个对nLength_的可取得最大价格的划分方案，及该划分方案下的价格
50+
double CalculateMaxProfit2(
51+
int nLength_,
52+
const double* pPriceTable_,
53+
double * pMaxProfitTable_,
54+
int nNum_)
55+
{
56+
// 所求取的 长度下最优划分方案下的价格，已经知道直接返回
57+
if (pMaxProfitTable_[nLength_] > 0)
58+
{
59+
return pMaxProfitTable_[nLength_];
60+
}
61+
62+
if (nLength_ == 0)
63+
{
64+
pMaxProfitTable_[0] = 0;
65+
return pMaxProfitTable_[0];
66+
}
67+
68+
if (nLength_ == 1)
69+
{
70+
pMaxProfitTable_[1] = pPriceTable_[1];
71+
return pMaxProfitTable_[1];
72+
}
73+
74+
double _nMaxProfit = 0;
75+
for (int _i = 1; _i <= nLength_; _i++)
76+
{
77+
double _nTempMax = pPriceTable_[_i] + CalculateMaxProfit2(nLength_ - _i, pPriceTable_, pMaxProfitTable_, nNum_);
78+
if (_nTempMax > _nMaxProfit)
79+
{
80+
_nMaxProfit = _nTempMax;
81+
}
82+
}
83+
84+
pMaxProfitTable_[nLength_] = _nMaxProfit;
85+
return pMaxProfitTable_[nLength_];
86+
}
87+
88+
// 算法输入：
89+
// nLength_ 总的长度
90+
// pPriceTable_ 一个数组。给出每个长度len和此长度对应的价格price
91+
// 输入限制：
92+
// 对于价格数组中，任意一组，满足 len > 0, price >= 0
93+
// 划分必须按整数长度进行
94+
// 算法目标：
95+
// 求取给定输入nLength_下，一个对nLength_的可取得最大价格的划分方案，及该划分方案下的价格
96+
double CalculateMaxProfitByIterration(
97+
int nLength_,
98+
const double* pPriceTable_,
99+
int nNum_)
100+
{
101+
// 分配内存用于存储，len及len下最优方案下价格
102+
double* _nMaxProfit = (double*)malloc(sizeof(double) * (nNum_ + 1));
103+
// 迭代
104+
// 循环不变式：
105+
// _nMaxProfit存储了上次len下最优划分下的价格
106+
// 初始时：
107+
// _nMaxProfit为空，上次len不存在。符合。
108+
// 第0/1次迭代后，_nMaxProfit分别存储0/1长度下最优方案下价格
109+
110+
// 某次迭代_i = len
111+
// 依据循环不变式，0,1,...,len-1下最优方案及其下价格均已经存储于_nMaxProfit
112+
// 依据
113+
// 长度为n的最优划分 = max
114+
// (
115+
// 1 + 长度为n-1的最优划分
116+
// 2 + 长度为n-2的最优划分
117+
// ...
118+
// n + 长度为0的最优划分
119+
// )
120+
// 可以直接利用已有结果得到len下最优方案及其下价格
121+
// 综合，循环不变式成立
122+
for (int _i = 0; _i <= nLength_; _i++)
123+
{
124+
// 从低到高
125+
if (_i == 0)
126+
{
127+
_nMaxProfit[0] = 0;
128+
}
129+
else if (_i == 1)
130+
{
131+
_nMaxProfit[1] = pPriceTable_[1];
132+
}
133+
else
134+
{
135+
_nMaxProfit[_i] = -1;
136+
double _nTempMaxProfit = -1;
137+
for (int _j = 1; _j <= _i; _j++)
138+
{
139+
_nTempMaxProfit = pPriceTable_[_j] + _nMaxProfit[_i - _j];
140+
if (_nTempMaxProfit > _nMaxProfit[_i])
141+
{
142+
_nMaxProfit[_i] = _nTempMaxProfit;
143+
}
144+
}
145+
}
146+
}
147+
148+
return _nMaxProfit[nLength_];
149+
}
150+

‎Design/DynamicPlanning/MaxProfit.h‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
// Author : XuBenHao
2+
// Version : 1.0.0
3+
// Mail : xbh370970843@163.com
4+
// Copyright : XuBenHao 2020 - 2030
5+
6+
#ifndef AILIB_DESIGN_DP_MAXPROFIT_H
7+
#define AILIB_DESIGN_DP_MAXPROFIT_H
8+
#include "..\..\stdafx.h"
9+
10+
extern "C" ALGORITHMLIB double CalculateMaxProfit1(int nLength_, const double* pPriceTable_, int nNum_);
11+
extern "C" ALGORITHMLIB double CalculateMaxProfit2(int nLength_, const double* pPriceTable_, double * pMaxProfitTable_, int nNum_);
12+
extern "C" ALGORITHMLIB double CalculateMaxProfitByIterration(int nLength_, const double* pPriceTable_, int nNum_);
13+
#endif

‎Design/DynamicPlanning/MinExpectTimes.cpp‎

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
#define ALGORITHMLIB __declspec(dllexport)
2+
#include "..\..\DataStruct\Array\DynArray.h"
3+
#include "MinExpectTimes.h"
4+
5+
double CalculateMinExpectTimes(
6+
const double* pArr_,
7+
int nS_,
8+
int nE_)
9+
{
10+
// 问题：
11+
// 给定 k1,k2,...,kn个数值
12+
// 满足k1< k2 < ... < kn
13+
// 给定
14+
// d0 代表所有小于 k1的数值
15+
// dn 代表所有大于kn的数值
16+
// di 代表所有大于ki且小于k(i+1)的数值
17+
// 已经知道
18+
// 一次搜索输入中，输入值为
19+
// ki的概率为pi
20+
// di的概率为qi
21+
22+
// 问，我们该如何组织k1,k2,...,kn这n个元素所构成的二叉搜索树
23+
// 来达到一次给定输入下预期搜索中节点比较次数最少的效果。
24+
25+
// 问题初步分析：
26+
// 1. 给定n个有序元素k1 < k2 < ... < kn
27+
// 若将该n个元素用二叉搜索树存储，则，对应的二叉搜索树具有多种可能
28+
// 2. 搜索中对于不在二叉搜索树元素集合中的元素，我们总是在比较到了二叉搜索树的叶子节点后，
29+
// 才能确定该元素不存在，此时的比较次数我们可以记为 比较到对应叶子节点的比较次数 + 1
30+
// 3. 对于二叉搜索树中存在的元素，一次搜索需要比较的次数，等于二叉搜索树中此元素的树高。
31+
// 我们规定根节点树高为1
32+
// 孩子节点树高 = 父亲节点树高 + 1
33+
34+
// 对于要求解的问题
35+
// 我们的输入是
36+
// n个概率值，代表的是 我们有序集合n个元素每个元素在一次搜索中出现的频率
37+
// n+1个概率值，代表的是 不在我们有序集合n个元素的n+1个可能区间中一次搜索时的概率
38+
39+
// 确立一棵二叉树首先要确立根节点
40+
// 对于一棵给定的二叉树，期望是已知的
41+
// 树的期望 = 所有树中非叶子节点树高 * 该节点对应概率 + 所有非树中节点【叶子节点】树高 * 该节点对应概率
42+
// = 左子树所有节点树高 * 该节点对应概率 + 右子树所有节点树高 * 该节点对应概率 + 根节点树高 * 根节点概率
43+
// = 左子树的期望 + 左子树所有节点概率 + 右子树期望 + 右子树所有节点概率 + 根节点树高 * 根节点概率
44+
// = 左子树的期望 + 右子树的期望 + 树中所有节点概率
45+
46+
// 假设对于给定一棵树是最优二叉树，即该树下执行一次搜索预期比较次数最少
47+
// 可以证明该树的左子树，右子树也是最优二叉树
48+
// 我们对树分析，其根节点可能为k1,...,kn中任意一个
49+
// 我们有
50+
// 最优二叉树 =
51+
// {
52+
// 根节点为k1 + 左最优二叉树 + 右最优二叉树,
53+
// ...
54+
// 根节点为kn + 左最优二叉树 + 右最优二叉树,
55+
// }
56+
int _nSize = nE_ - nS_;
57+
if (_nSize == 1)
58+
{
59+
return *(pArr_ + nS_);
60+
}
61+
62+
if (_nSize == 0)
63+
{
64+
return 0.0;
65+
}
66+
67+
if (_nSize % 2 == 0)
68+
{
69+
throw "Input error";
70+
}
71+
72+
double _nSum = 0.0;
73+
for (int _i = 0; _i < _nSize; _i++)
74+
{
75+
_nSum += *(pArr_ + _i + nS_);
76+
}
77+
78+
double _nMinExpect = _nSum
79+
+ CalculateMinExpectTimes(pArr_, nS_, nS_ + 1)
80+
+ CalculateMinExpectTimes(pArr_, nS_ + 2, nE_);
81+
for (int _i = 3; _i < _nSize; _i = _i + 2)
82+
{
83+
double _nExpect = _nSum
84+
+ CalculateMinExpectTimes(pArr_, nS_, nS_ + _i)
85+
+ CalculateMinExpectTimes(pArr_, nS_ + _i + 1, nE_);
86+
if (_nExpect < _nMinExpect)
87+
{
88+
_nMinExpect = _nExpect;
89+
}
90+
}
91+
92+
return _nMinExpect;
93+
}
94+
95+
// 算法输入：
96+
// 一个数组起始地址
97+
// 一个区间【首元素位置，尾后元素位置】
98+
99+
// 区间内元素为我们要求解的构成最优二叉树的叶子节点，非叶子节点元素及其被搜索到的概率
100+
// 返回值：
101+
// 区间内元素按最优二叉树组织下，一次搜索预期比较次数
102+
103+
// 算法正确性证明：
104+
// 分治采用数学归纳法证明
105+
// 即预先假定算法正确
106+
107+
// 规模足够小时，
108+
// 即树中节点和非节点元素个数小于等于1，二叉树唯一，立即求解。得到唯一解，同时也是最优解。
109+
110+
// 规模为 nS_, nE_时，
111+
// 依据数学归纳法，所有比此规模更小的规模，算法均可正确求解。
112+
// 对规模 nS_, nE_
113+
// 当我们选定此规模下根节点时，
114+
// 便将规模 nS_, nE_划分为两个更小的规模
115+
// 算法在两个较小规模下，可以正确求解。
116+
// 且规模 nS_, nE_和两个较小规模存在以下关系
117+
// 规模 nS_, nE_的解 = 两个较小规模解的和 + nS_到nE_所有概率之和
118+
119+
// 对规模 nS_, nE_的所有可能根节点划分
120+
// 我们依次求取每种划分下的最优解，
121+
// 从所有划分中，选取最优解最优的。
122+
// 则，我们将得到 nS_, nE_规模下，最优的解。
123+
// 综合，我们的算法对于任何给定的规模，总是可以求出该规模下的最优解。

‎Design/DynamicPlanning/MinExpectTimes.h‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
// Author : XuBenHao
2+
// Version : 1.0.0
3+
// Mail : xbh370970843@163.com
4+
// Copyright : XuBenHao 2020 - 2030
5+
6+
#ifndef AILIB_DESIGN_DP_MINEXPECTTIMES_H
7+
#define AILIB_DESIGN_DP_MINEXPECTTIMES_H
8+
#include "..\..\stdafx.h"
9+
extern "C" ALGORITHMLIB double CalculateMinExpectTimes(
10+
const double* pArr_,
11+
int nS_,
12+
int nE_);
13+
14+
#endif
15+

0 commit comments

Comments
 (0)