C++不知算法系列之深入动态规划算法思想-创新互联

前面写过一篇博文，介绍了什么是动态规划算法。动态规划算法的大特点，原始问题可以通过分解成规模更小的子问题来解决，子问题之间互成依赖关系，先计算出来的子问题的结果会影响到后续子问题的结果。

有点类似于武侠片中，主角受伤后，一群江湖侠士排成一排，最后一人把真气传递给前面的、前面的再传递给他前面……如此传递，最后传递给主角，主角最终获取到所有人的真气。

真气传递过程中，每一个人就是一个子问题，如果每一个人传递出去的真气是个体大的，则最后主角获取到的真气必然也是大的。这便是动态规划的最优子结构的概念。

本文通过几个案例，深入探讨动态规划。

求解如下有向权重图中从A城市到E城市之间的最短路程。城市与城市之间的连接线上的数字表示城市之间的路程。

动态规划是一种从下向上的解决方案，也就是逆推思维。

顺着这个思路，本题目可以先计算离E最近的D层到E的最短路程。D层上有3个顶点，意味着需要单独计算3次。如此可见，原始问题是可以拆分成多个子问题进行解决的，符合动态规划的条件之一：存在子问题。

为了分析问题的方便，给每一个结点一个编号（如上图，字母后面的数字便是结点的编号）。并且把任一结点到E结点的最短路程存储在一维数组中(也称为db数组)。

• 从D层到E是直达的，权重值即是最小值，可以直接存储。

• C层到E层的路程计算原则。C4~E中间只经过D8，路程数为2，即C4～E的最短路程为2。但是，C5~E中间可以经过D8和D9，C5~D8~E的路程数是4，C5~D9~E的路程数是13，则需要在两者中选择最小值，即min(4,13)，或说C5~E的最短路程是4。C6~E的最短路程为14,C7~E的最短路程为5。

  Tips：

  路径计算法则 ：当前结点到中间结点的权重加上中间结点到最终结点的最小路程值。

  如C5到E结点可以通过中间结点D8、D9到达，即有2条可行路径。

  如计算C5~D8~……E的路程值：C2到D8的权重加上D8到E的最小路程值（可以从db数组中获取）。即：3+1。

  路径选择原则：当存在多条路径时，选择值最小的。如上分别计算出2条路程值(4，13)后，再选择最小值，如此能得到C5~E的路径值 4 是最小的。

• B层到E的最路短路程计算和上述是一样的。B2可以经过C4、C5、C6到达E，在3条路径中选择最小值min(4,9,17)，即B2~E最短路程为4。B3可以经过C6、C7到达E，同样在2条路径中选择最小值min(20,9)。即B2~E最短路径为9。

• A1可以经过B2、B3到达E，在2条路径中选择最小值，即min(8,12)。最终可知A~E的最短路程为8。

如上述流程可知，向上逆推过程中，求解到每一层到达E结点的最短路程后，再把最小值向上层提供，显然，最后所求解的值一定是最小值，也称为最优子结构思想。不仅能求解出A~E的最短路径，并且能求解出每一个结点到达E的最短路程。

动态规划算法中，有2个非常重要的信息需要获取：

• 存储子问题的状态信息(本题指子问题到最终结点的最短路程)。如上述演示图中的db一维数组。
• 另就是状态求解方程式。通过上述分析可知，f(v)=min( w(v,v1)+db(v1), w(v,v2)+db(v2),…… )。

问题域本身也有2个信息：

• 结点数据。
• 结点之间的关系数据。

#include#include

输出结果：

#include#includeusing namespace std;
int main(int argc, char** argv) {
	int money=0;
	cout<<"请输入零钱数:"<>money;
	//硬币类型
    int coins[5]= {1,5,10,21,25};
	//状态数组，零钱需要找回的硬币数
	vectordp(money+1, money+1);
	dp[0]=0;
	for(int i=1; i<=money; i++) {
		for(int j=0; i>=coins[j]; j++) {
             //求最小值            
			dp[i]=dp[i]< dp[ i-coins[j] ]+1 ? dp[i] : dp[ i-coins[j] ]+1;	    	
		}
	}
	cout<

N = 3, W = 6
wt = [ 1,2,7 ]
val = [4,3,2 ]

#include#includeusing namespace std;
int main(int argc, char** argv) {
	//物品信息
	int goods[3][3]= { {1,4},{2,3} };
	//背包容量
	int bagWeight=0;
	cout<<"请输入背包容量："<>bagWeight;
	//状态表
	int db[4][bagWeight+1]= {0};
	for(int i=0; i<4; i++) {
		for(int j=0; jwt ) {
				//如果背包不能装下物品，保留背包上一次的结果
				db[w][wt]=db[w-1][wt];
			} else {
				//能装下,计算本物品价值和剩余容量的大价值
				int val=goods[w-1][1] + db[w-1][ wt- goods[w-1][0] ];
				//背包原来的价值
				int val_= db[w-1][wt];
				//计算大值
				db[w][wt]=val>val_?val:val_;
			}
		}
	}
	for(int i=1; i<3; i++) {
		for(int j=1; j<=bagWeight; j++) {
			cout<