欢迎来到天天文库
浏览记录
ID:39869452
大小:1.07 MB
页数:134页
时间:2019-07-13
《ACM培训-动态规划》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、ACM培训动态规划动态规划的概念¢动态规划算法通常用来解决最优化问题。这些问题可能存在多个解,每个解具有一个值。我们希望找到一个具有最优(最大或最小)值的解。在动态规划算法中,主要关心的是找到一个最优解和求出最优解的值,而不是找出所有的最优解。例:计算斐波那契数:⎧0n=0⎪F(n)=⎨1n=1⎪⎩F(n−1)+F(n−2)n≥2n=5时分治法计算斐波那契数的过程。F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)算法0#include2、ream>usingnamespacestd;intf(intn){if(n==13、4、n==0)return1;elsereturnf(n-1)+f(n-2);}缺点:重复计算,浪费时间main(){intn;cin>>n;cout<5、m>usingnamespacestd;intsave[100];intf(intn){if(save[n]!=0)returnsave[n];if(n==16、7、n==0){save[n]=1;returnsave[n];}save[n]=f(n-1)+f(n-2);returnsave[n];}main(){memset(save,0,sizeof(save));intn;cin>>n;cout<8、化,正符合了这个要求.用动态规划法求解的问题具有特征:V能够分解为相互重叠的若干子问题;V满足最优性原理(也称最优子结构性质):该问题的最优解中也包含着其子问题的最优解。动态规划法设计算法一般分成三个阶段:(1)分段:将原问题分解为若干个相互重叠的子问题;(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式;(3)求解:利用递推式自底向上计算,实现动态规划过程。∑动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。数字三角形¢给你一个数字三角形,形式如下:12349、5678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形的演化¢给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形¢状态转移方程:¢f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}¢正面思路分析问题,得出一个非常简单的递归过程:¢f1=f(i-1,j+1);f2=f(i-1,j);¢if(f1>f2)f=f1+a[i,j];elsef=f2+a[i,j];算法0#include10、usingnamespacestd;#definemax100inta[max][max];intsum(inti,intj,intn){if(i==n-1)returna[i][j];else{if(sum(i+1,j,n)>sum(i+1,j+1,n))returnsum(i+1,j,n)+a[i][j];elsereturnsum(i+1,j+1,n)+a[i][j];}}main(){inti,j,t;缺点:重复计算,浪费时间intn;cin>>n;for(i=0;i11、(j=0;j<=i;j++)cin>>a[i][j];cout<12、直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,#includeusingnamespacestd;算法1#definemax100inta[max][max];intopt[max][max];intsum(inti,intj,intn){if(opt[i][j]!=0)returnopt[i]
2、ream>usingnamespacestd;intf(intn){if(n==1
3、
4、n==0)return1;elsereturnf(n-1)+f(n-2);}缺点:重复计算,浪费时间main(){intn;cin>>n;cout<5、m>usingnamespacestd;intsave[100];intf(intn){if(save[n]!=0)returnsave[n];if(n==16、7、n==0){save[n]=1;returnsave[n];}save[n]=f(n-1)+f(n-2);returnsave[n];}main(){memset(save,0,sizeof(save));intn;cin>>n;cout<8、化,正符合了这个要求.用动态规划法求解的问题具有特征:V能够分解为相互重叠的若干子问题;V满足最优性原理(也称最优子结构性质):该问题的最优解中也包含着其子问题的最优解。动态规划法设计算法一般分成三个阶段:(1)分段:将原问题分解为若干个相互重叠的子问题;(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式;(3)求解:利用递推式自底向上计算,实现动态规划过程。∑动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。数字三角形¢给你一个数字三角形,形式如下:12349、5678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形的演化¢给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形¢状态转移方程:¢f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}¢正面思路分析问题,得出一个非常简单的递归过程:¢f1=f(i-1,j+1);f2=f(i-1,j);¢if(f1>f2)f=f1+a[i,j];elsef=f2+a[i,j];算法0#include10、usingnamespacestd;#definemax100inta[max][max];intsum(inti,intj,intn){if(i==n-1)returna[i][j];else{if(sum(i+1,j,n)>sum(i+1,j+1,n))returnsum(i+1,j,n)+a[i][j];elsereturnsum(i+1,j+1,n)+a[i][j];}}main(){inti,j,t;缺点:重复计算,浪费时间intn;cin>>n;for(i=0;i11、(j=0;j<=i;j++)cin>>a[i][j];cout<12、直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,#includeusingnamespacestd;算法1#definemax100inta[max][max];intopt[max][max];intsum(inti,intj,intn){if(opt[i][j]!=0)returnopt[i]
5、m>usingnamespacestd;intsave[100];intf(intn){if(save[n]!=0)returnsave[n];if(n==1
6、
7、n==0){save[n]=1;returnsave[n];}save[n]=f(n-1)+f(n-2);returnsave[n];}main(){memset(save,0,sizeof(save));intn;cin>>n;cout<8、化,正符合了这个要求.用动态规划法求解的问题具有特征:V能够分解为相互重叠的若干子问题;V满足最优性原理(也称最优子结构性质):该问题的最优解中也包含着其子问题的最优解。动态规划法设计算法一般分成三个阶段:(1)分段:将原问题分解为若干个相互重叠的子问题;(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式;(3)求解:利用递推式自底向上计算,实现动态规划过程。∑动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。数字三角形¢给你一个数字三角形,形式如下:12349、5678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形的演化¢给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形¢状态转移方程:¢f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}¢正面思路分析问题,得出一个非常简单的递归过程:¢f1=f(i-1,j+1);f2=f(i-1,j);¢if(f1>f2)f=f1+a[i,j];elsef=f2+a[i,j];算法0#include10、usingnamespacestd;#definemax100inta[max][max];intsum(inti,intj,intn){if(i==n-1)returna[i][j];else{if(sum(i+1,j,n)>sum(i+1,j+1,n))returnsum(i+1,j,n)+a[i][j];elsereturnsum(i+1,j+1,n)+a[i][j];}}main(){inti,j,t;缺点:重复计算,浪费时间intn;cin>>n;for(i=0;i11、(j=0;j<=i;j++)cin>>a[i][j];cout<12、直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,#includeusingnamespacestd;算法1#definemax100inta[max][max];intopt[max][max];intsum(inti,intj,intn){if(opt[i][j]!=0)returnopt[i]
8、化,正符合了这个要求.用动态规划法求解的问题具有特征:V能够分解为相互重叠的若干子问题;V满足最优性原理(也称最优子结构性质):该问题的最优解中也包含着其子问题的最优解。动态规划法设计算法一般分成三个阶段:(1)分段:将原问题分解为若干个相互重叠的子问题;(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式;(3)求解:利用递推式自底向上计算,实现动态规划过程。∑动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。数字三角形¢给你一个数字三角形,形式如下:1234
9、5678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形的演化¢给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形¢状态转移方程:¢f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}¢正面思路分析问题,得出一个非常简单的递归过程:¢f1=f(i-1,j+1);f2=f(i-1,j);¢if(f1>f2)f=f1+a[i,j];elsef=f2+a[i,j];算法0#include
10、usingnamespacestd;#definemax100inta[max][max];intsum(inti,intj,intn){if(i==n-1)returna[i][j];else{if(sum(i+1,j,n)>sum(i+1,j+1,n))returnsum(i+1,j,n)+a[i][j];elsereturnsum(i+1,j+1,n)+a[i][j];}}main(){inti,j,t;缺点:重复计算,浪费时间intn;cin>>n;for(i=0;i11、(j=0;j<=i;j++)cin>>a[i][j];cout<12、直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,#includeusingnamespacestd;算法1#definemax100inta[max][max];intopt[max][max];intsum(inti,intj,intn){if(opt[i][j]!=0)returnopt[i]
11、(j=0;j<=i;j++)cin>>a[i][j];cout<12、直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,#includeusingnamespacestd;算法1#definemax100inta[max][max];intopt[max][max];intsum(inti,intj,intn){if(opt[i][j]!=0)returnopt[i]
12、直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,#includeusingnamespacestd;算法1#definemax100inta[max][max];intopt[max][max];intsum(inti,intj,intn){if(opt[i][j]!=0)returnopt[i]
此文档下载收益归作者所有