方法概述: 发展及研究内容
动态规划(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);
}
}
- 大小: 43.1 KB
- 大小: 19.3 KB
- 大小: 57 KB
分享到:
相关推荐
动态规划dynamic programming
算法数据结构——动态规划算法(Dynamic Programming)超详细总结加应用案例讲解算法数据结构——动态规划算法(Dynamic Programming)超详细总结加应用案例讲解算法数据结构——动态规划算法(Dynamic Programming...
引入这两个概念之后,我们如何判断一个问题能否使用DP解决呢?能将大问题拆成几个小问题,且满足无后效性、最优子结构性质。3. DP的典型应用:DAG最短路问题很简
Dynamic Programming http://hi.baidu.com/leokan/blog/item/919a7f0eaa1759cc7acbe1c7.html
Adaptive Dynamic Programming 自适应动态规划的入门介绍。令初学者简明扼要的了解ADP的核心思想。
动态规划(Dynamic programming)详细解读
动态规划(Dynamic Programming,DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划经常在各种最优化问题中发挥...
Dynamic Programming for Interviews,
动态规划(Dynamic Programming, DP)是一种有效的计算机算法设计技术,主要用于解决具有重叠子问题和最优子结构特征的问题,这些问题是无法直接得出最优解,但可以通过求解其各个子问题的最优解来构造原问题的最优...
动态规划(Dynamic Programming,简称DP)是一种常用的解决多阶段决策过程最优化问题的方法。它将原问题分解为若干个子问题,通过解决子问题得到原问题的最优解。动态规划通常用于解决最优化问题,比如最短路径、...
DYNAMIC PROGRAMMING AND OPTIMAL CONTROL
"Approximate Dynamic Programming: Solving the Curses of Dimensionality" 介绍了动态规划的算法、理论和应用。是学习动态规划的极佳教材
动态规划经典书籍,动态规划的技术和艺术 The Art and Theory of Dynamic Programming
DNA Sequence Alignment Using Dynamic Programming by C#
Neuro-Dynamic Programming by Dimitri P. Bertsekas and John Tsitsiklis
《Handbook of Learning and Approximate Dynamic Programming》,作者 Jennie Si, Andy Barto, Warren Powell, Donald Wunschauth. 仔细阐述了自适应动态规划,很详细
包括实现 缩写 所有构造 位掩码 加泰罗尼亚语数字 爬楼梯 组合总和 iv 编辑距离 阶乘 快速斐波那契 斐波那契 嘶嘶声 弗洛伊德·沃歇尔 整数分区 遍历子掩码 K 表示聚类张量流 ... 分词
上海财经大学 2019年暑期课程之动态规划,dynamic programming SUFE 2019 Summer School