admin管理员组文章数量:1530017
1 算法思想
动态规划
1.1含义
把问题分解成多阶段或多个子问题,顺序求解各个子问题,最后一个子问题就是初始问题的解。
概念
阶段: 问题分成的顺序的几个环节。例如最长递增子序列中每个字符就是一个阶段。
状态: 描述问题当前状况的数字量。可以表示状态特征,例如最长递增子序列中dp[x]表示以x结尾的字符串的最长递增子序列长度,就是一个状态。
决策:从某阶段状态到下一阶段某状态的选择。例如数塔问题中取第i行第j个数有两种方案: 取第i-1行第j1个数或取第i-1行第j个数后再取第i行第j个数。
状态转移方程:数字量之间的递推关系。例如最长递增子序列中状态转移方程为:
F[i]={1, i=1
{max{1, F[j] + 1}, j < i && aj>=ai
1.2 性质
最优子结构: 问题最优解包含子问题的最优解。
无后效性:某阶段状态(数字量例如dp[x])确定后,就不受这个状态以后决策的影响。即以后不影响以前。
解释:
最优子结构: 数塔问题中,假设9->12->10->8->10是最优路径,那么12->10->8->1也是12到达最后一层的最大和
1.3适用
子问题重叠+无后效性+最优子结构的问题
为了解决子问题重叠的问题,可以采用备忘录法,用表格记录到已经计算过的状态值。
1.4通用解法
动态规划算法: 1 确定状态转移方程 2 初始化边界状态的值 3 设定循环来递推状态的值 4 返回目标状态的值 |
1.5经典例题讲解
0-1背包问题
不同草药,采每一株需要一些时间,每一株有自己价值,如何让采到的价值最大。
输入:第一行有两个整数T(1<=T<=1000)和M(1<=M<=100),T代表总共能够用来采药的时间,M代表山洞里的草药数目。
接下来的M行,每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值
输出:在规定时间内,可以采到的草药的最大总价值
问题抽象:
有一个容量为V的背包,和一些物品。这些物品分别有两个属性,体积w和价值v,每种物品只有1个。
要求背包装下价值尽可能多的物品,求该最大价值,背包可以不被装满。
分析状态转移方程:
用dp[i][j]表示总体积不超过j的情况下,前i个物品能达到的最大价值。
边界状态:
dp[0][j] = 0,(0<=j<=V)
根据每个物品是否放入背包,每个状态有两个状态转移来源
若物品i放入背包,设其体积为w,价值为v,则有
dp[i][j]=dp[i-1][j-w] + v
不放入背包,则有
dp[i][j]=dp[i-1][j]
所以有:
dp[i][j]=max{ dp[i-1][j-w] + v, dp[i-1][j]}
注意: j-w的值不能为负数
//定义背包 typedef struct List { int w;//体积 int v;//价值 }List;
int max(int a,int b) { return a > b ? a:b; }
int main(int argc,char* argv[]) { int s;//总容积 int n;//n行 int i,j; while(EOF!=scanf("%d %d",&s,&n)) { List list[101]; //int dp[101][1001]; int dp[1001];//优化 for(i = 1 ; i <= n ; i++) { scanf("%d %d",&list[i].w,&list[i].v); } //初始化边界状态的值 for(i = 0 ; i <= s ; i++) { //dp[0][i] = 0; dp[i] = 0; }
//设定循环来递推状态的值 //对于时间足够的情况,状态来源是:dp[i][j]为两者之中的最大值 for(i = 1 ; i <= n ; i++) { for(j = s; j >= list[i].w ; j--) { //dp[i][j] = max(dp[i-1][j],dp[i-1][j-list[i].w] + list[i].v); //优化:必须倒序更新每个dp[j]的值,j小于list[i].w的各dp[j]不做更新,保持原值,即等价与dp[i][j] = dp[i-1][j] dp[j] = max(dp[j],dp[j-list[i].w] + list[i].v); } /* for(j = list[i].w-1; j >= 0 ; j--) { dp[i][j] = dp[i-1][j]; } */ }
//返回目标状态的值 //printf("%d\n",dp[n][s]); printf("%d\n",dp[s]); } system("pause"); getchar(); return 0; } |
1.6动态规划与其他算法的区别
动态规划与贪心的区别:
贪心是在当前状态进行局部最优的选择,这种选择以来过去所做的选择。与贪心算法不同的是,动态规划分解的子问题往往不独立
动态规划与分治的联系:
基本思想都是将待求解问题分解成若干个子问题,先求解子问题,然后从子问题的解得到原问题的解。
1.7时间复杂度与空间复杂度
时间复杂度=状态数量*每次状态转移的时间复杂度
空间复杂度=申请的数组大小
2 动态规划系列
类别-编号 |
题目 |
遁去的1 |
来源 |
1 |
N阶楼梯上楼问题 N阶楼梯上楼问题:一次可以走两阶或者一阶,问有多少种上楼方式(要求采用非递归) |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186333 |
2 |
不容易系列之一 给N个网友写信,所有信全部装错信封有多少种可能的错误方式 |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186349 |
3 |
最长递增子序列问题 在一个已知的序列{a1,a2,...,an}中,取出若干数组组成的序列{ai1,ai2,..,aim},其中下标i1,i2,...,im保持递增,即新增数列中的各个数之间依旧保持原数列中的先后顺序,那么称新的序列为原序列的一个子序列。若在序列中,下标ix > iy时,aix > aiy,称这个子序列为原序列的一个递增子序列。 |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186395 |
4 |
拦截导弹 导弹系统有缺陷,后面炮弹高度<=前一发高度。计算系统能拦截多少导弹。拦截时,必须按照时间顺序,不允许先拦截后面的导弹再拦截前面的导弹。 输入:每组输入两行。第一行:导弹数量k(k<=25)。第二行:k个整数,表示第k枚导弹的高度,按时间顺序,空格分隔 输出:每组输出一行,包含一个整数,表示能拦截多少导弹。 |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186409 |
5 |
最长公共子序列 字符串S中按照先后顺序依次取出若干字符,并将它们排列成一个新的字符串,这个字符串就称为原字符串的子串。有2个字符串S1和S2,求字符串S3同时为S1和S2的子串,且要求它的长度最长,确定这个长度。
|
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186443 |
6 |
搬寝室 n件物品,n<2000.准备搬2*k(<=n)件物品。每搬一次的疲劳度和左右手之间的重量差的平方成正比。请求出办完这2*k件物品后的最低疲劳度是多少 输入:每组输入数据有2行,第一行有2个数n,k(2<=2*k<=n<2000),第二行有n个整数,分别表示n件物品的重量(<2的15次方) 输出:对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行. |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186477 |
7 |
Greedy Tino 有一堆柑橘,重量为0到2000,总重量不大于2000。从中取出两堆放在扁担两头,且两头重量相等,问符合条件的的每堆重量最大是多少。没有符合条件的分堆方式则输出-1 输入:第一行时t,表示t个测试用例,对每个测试用例,包含一个数字n,表名橘子数。第二行有n个数字,表明每个橘子的重量,1<=n<=100.如果是因为存在重量为0的橘子,导致扁担两边重量为0,那么应该输出0,否则输出-1 |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186505 |
8 |
采药 不同草药,采每一株需要一些时间,每一株有自己价值,如何让采到的价值最大。 输入:第一行有两个整数T(1<=T<=1000)和M(1<=M<=100),T代表总共能够用来采药的时间,M代表山洞里的草药数目。 接下来的M行,每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值 输出:在规定时间内,可以猜到的草药的最大总价值 |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186535 |
9 |
Piggy-Bank 有一个储蓄罐,告知空的质量和当前重量,并给定一些钱币的价值和相应的重量,求储蓄罐中最少有多少现金。 输入:包含T组测试用例。第一行。每一个测试用例包含2个整数E和F,表明空储蓄罐的重量和装满钱的重量。<=10,000g,第二行是每个测试用例,包含一个整数N(1<=N<=500), 给出了各种硬币的数量。接下来是N行,每行表示一种硬币类型,每行包括2个整数,P,W(1<=p<=50000,1<=W<=10000),p是价值,W是重量 输出: 储蓄罐中最少有多少钱 |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/97750459 |
10 |
珍惜现在,感恩生活 支援灾区。你有n元,市场有m种大米,每种打磨都是袋装产品,价格不等,并且只能整袋购买。你最多能采购多少公斤粮食 输入:第一行1个正整数C(表示有C组测试用例),每组测试用例的第一行时两个整数n和m(1<=n<=100,1<=m<=100),分别表示经费的金额和大米的种类,然后是m行数据。 每行包括3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20),分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。 输出:输出能够购买大米最多重量,经费可以不用完 |
|
计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186603 |
11 |
连续子数组的最大和: 输入一个整形数组,数组里有整数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的 最大值。要求时间复杂度为O(n) |
|
剑指offer https://blog.csdn/qingyuanluofeng/article/details/39186633 |
12 |
数塔问题 有形如右图的一个数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的数值和最大 |
|
算法设计与分析 https://blog.csdn/qingyuanluofeng/article/details/47189313 |
13 |
TSP之货郎担问题 |
版权声明:本文标题:算法 64式 8、动态规划算法整理 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1726764133a1083399.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论