动态规划（dynamic programming）

方法概述: 发展及研究内容

动态规划(dynamic programming)是运筹学的一个分支，20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、资源分配、设备更新等问题，用动态规划比用其它方法求解更为方便。

 

方法概述: 基本思想

A.动态规划的思想实质是分治思想和解决冗余。

B.与分治法类似的是，将原问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

C.与分治法不同的是，经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分（子问题或子子问题）被重复计算了很多次。

D.如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免重复计算、节省时间。动态规划法用一个表来记录所有已解的子问题的答案。

E.这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表方式。

 

方法概述: 求解步骤

1、找出最优解的性质，并刻画其结构特征；

2、递归地定义最优值（写出动态规划方程）；

3、以自底向上的方式计算出最优值；

4、根据计算最优值时记录的信息，构造最优解。

注：

－步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略；

－若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息是构造最优解的基础

 

方法概述: 适用条件

动态规划法的有效性依赖于问题本身所具有的两个重要性质

最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

 

例1：多段图的最短路问题

多段图：设G=<V,E>是一个有向连通图，其中|V|=n, |E|=m,  V有划分{V1,V2,···,Vk}，这里V1 ={s},s称为源点， Vk ={t},t称为终点，其中k ≥ 2 。对于每条有向边<u,v> ∈ E都存在Vi ∈ V，使得u ∈ Vi和v ∈ Vi+1, 其中1≤i<k且每条边<u,v>均附有代价C(u,v)，则称G是一个k段图。

 

 

最短路：从源点s到终点t的整条路上的代价之和为最小。

每个子集Vi构成图中的一段。由于E的约束，每条从s到t的路径都是从第一段开始，然后顺次经过第2段，第3段，···，最后在第k段终止。对于每条从s到t的路径，可以把它看成在k-2个阶段中做出的某个决策序列的相应结果。

假设s,v2,v3,···,vk-1,t是一条从s到t的最短路径，还假定从源点s（初始状态）开始，已做出了到结点v2的决策（初始决策），因此v2就是初始决策所产生的状态。如果把v2看成是原问题的一个子问题的初始状态，解这个子问题就是找出一条由v2到t的最短路径。这条路径显然是 v2,v3,···,vk-1,t，否则设v2,q3,···,qk-1,t是一条由v2到t的更短路径，则s,v2,q3,···,qk-1,t是一条比路径s,v2,v3,···,vk-1,t 更短的由s到t的路径，与假设矛盾，故最优化原理成立。

向前处理法：设P(i,j)是从Vi中的点j到t的一条最短路，cost(i,j)是这条路线的耗费。由后向前推算，得到

 

 

 

 

 

                      cost(i,j)=min{C(j,r)+cost(i+1,r)} 

                  cost(4,9)=4 cost(4,10) =2  cost(4,11)=5

                  cost(3,6)=min{6+cost(4,9),5+cost(4,10)}

                                   =min{6+4,5+2}=7

从第3段的顶点6到t的最短路径是6-10-t

 

 cost(3,7)=min{4+cost(4,9),3+cost(4,10)} =min{4+4,3+2}=5

从第3段的顶点7到t的最短路径是7-10-t

cost(3,8)=7

从第3段的顶点8到t的最短路径是8-10-t

cost(2,2)=7 从第2段顶点2到t的最短路是2-7-10-t

cost(2,3)=9从第2段顶点3到t的最短路是3-6-10-t

cost(2,4)=18从第2段顶点4到t的最短路是4-8-10-t

cost(2,5)=15从第2段顶点5到t的最短路是5-8-10-t

cost(1,1)=16 从第1段顶点1到t的最短路径由两条：

                     1-2-7-10-t和1-3-6-10-t

用D(i,j)表示使C(j,r)+cost(i+1,r)取得最小值
的r，则在上述求解过程中同时得到：

D(3,6)=10, D(3,7)=10, D(3,8)=10

D(2,2)=7, D(2,3)=6, D(2,4)=8

D(2,5)=8, D(1,1)=2

设从s到t的最短路径为s,w2,w3,···,wk-1,t

则有w2=D(1,1)=2

w3= D(2,D(1,1))=D(2,2)=7

w4=D(3,D(2,D(1,1)))=D(3,D(2,2))=D(3,7)=10

所以这条路径是1-2-7-10-t

 

为了便于描述算法，对一个k段图的顶点，按段的顺序给它的每个顶点编号。设图中有n个顶点，则编号为1，2，···，n。首先，给s编为1号；然后给V2中的各个顶点分别编为2，3， ··· ，| V2 |+1号；以此类推，最后t编号为n。

这样编号使Vi+1中的任何顶点的编号大于Vi中所有顶点的编号。

于是，可以按n-1,n-2,···,1的顺序计算出cost(i,j)和D(i,j)。算法中可以利用顺序编号的特点，而不再考虑顶点所在的段。

设顶点的编号已知，边已知及边的代价函
数C(i,j)已知。用cost[i]表示顶点i到t的最小
代价， 1≤i ≤n。用D[i]表示从顶点i到t的最短路径上顶点i的后继顶点号，用P[i]表示最短路径经过第i级的顶点号， 1≤i ≤k

 

例2

对于由从1到N (1 <= N <= 39)这N个连续的整数组成的集合来说，我们有时可以将集合分成两个部分和相同的子集合。
例如，N=3时，可以将集合{1, 2, 3} 分为{1,2}和{3}。此时称有一种方式（即与顺序无关）。
N=7时，共有四种方式可以将集合{1, 2, 3, ..., 7} 分为两个部分和相同的子集合：
{1,6,7} 和 {2,3,4,5} 
{2,5,7} 和 {1,3,4,6} 
{3,4,7} 和 {1,2,5,6} 
{1,2,4,7} 和 {3,5,6} 
输入：程序从标准输入读入数据，只有一组测试用例。如上所述的N。
输出：方式数。若不存在这样的拆分，则输出0。

代码实现：

#include<stdio.h>

void main(){

	int i,j,x,y,flag,sum;
	int input,outresult;
	int num[40][410] = {0};
	num[0][0] = 1;

	scanf("%d",&input);

	x = input, y = (1 + input)*input/2;
	sum = y/2;

	flag = y%2;

	if(flag == 1)
		printf("0\n");

	else{
		for(i=1;i<=x;i++){
			for(j=1;j<=y/2;j++)
				if(i<=j)
					num[i][j] = num[i-1][j] + num[i-1][j-i];
				else
					num[i][j] = num[i-1][j];
		}

		outresult = num[x][sum];
		printf("%d\n",outresult);
	}


}