1 / 17
文档名称:

动态规划.docx

格式:docx   大小:39KB   页数:17页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

动态规划.docx

上传人:国霞穿越 2022/6/25 文件大小:39 KB

下载得到文件列表

动态规划.docx

相关文档

文档介绍

文档介绍:动态规划
一、背包问题
1、0/1背包[问题背景及描述]
Bessie正在减肥,所以她规定每天不能吃超过C(10<=C<=35,000)卡路里的食物。农民John在戏弄她,在她面前放了B(1<=B<=21)捅食物。每桶内都有某个单位卡
38920715530029917015865
6{最多能拦截的导弹数}
2{要拦截所有导弹最少要配备的系统数}
2、某农场有一个由按编号次序排列的n根木桩构成的首尾不相连的围栏。现要在这个围栏中选取一些木桩,按照原有的编号次序排列之后,这些木桩的高度成为一个升序序列。所谓的升序序列就是序列中的任何一个数都不小于它之前的任何一个数。试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数t最大,并求出选出t根木桩的方案总数C。例如:围栏由高度分别为10,1,9,8,7,6,3,4,6的木桩构成,则选出的高度为1,3,4,6的木桩是满足题意的选取方案。
输入格式:文件中的第1行只有一个数m,表明随后有m个问题的描述信息。每个问题的描述信息格式为nh1h2h3,,,hn
输出格式:依次输出每个问题中t和c的解。每行输出一个问题的解。
例如
输入:
3
91019876346
310070102
6403723899112
输出:
41
22
33
3、合唱队形
(/dpr/c/cpp)
【问题描述】
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为Tl,T2,…,TK,则他们的身高满足
Tl<...<Ti>Ti+l>…〉TK(1〈二i<=K)。你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
【输入文件】
(2<=N<=100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
【输出文件】
,这一行只包含一个整数,就是最少需要几位同学出列。
【样例输入】
8
186186150200160130197220
【样例输出】
4
【数据规模】
对于50%的数据,保证有n<=20;对于全部的数据,保证有n<=100。
三、数列的连续最大和
1、数列的连续最大和,顾名思义,就是在一个长度为n的数列{An}中,求i,j(1<=i<=j<=n),使得数列{An}中,第i个元素到第j个元素之间,所有元素的和最大。
分析:
以第i个数结尾的最大连续和序列,可能存在两种选择:情形一:只包含Ai
情形二:包含Ai和以Ai-1结尾的最大连续和序列
设F(i)表示以第i个数结尾的最大连续和
转移方程:
F(i)=max{Ai,F(i-1)+Ai}
边界:F(1)=A1
要求的结果为max{F(i)|1<=i<=n}
仔细思考题目后,符合动态规划条件。
用ans[i]表示包含数列第i项的前i个元素的最大和,数组no存放数列元素,则状态转移方程为:
ans[0]=0;
ans[i]=max{ans[i-1]+no[i],no[i]}时间复杂度为O(n)核心程序代码:
best:=-maxlongint;
temp:=0;
fori:=1tondo
begin
inc(temp,no[i]);
iftemp>bestthenbest:=temp;
iftemp<0thentemp:=0;
end;
2、最大子序和
问题描述
输入一个长度为n的整数序列(A1,A2,……,An),从中找出一段连续的长度不超过M的子序列,使得这个序列的和最大。
例如:序列1,-3,5,1,-2,3
当M=2或3时S=5+1=6
当M=4时S=5+1+(-2)+3=7
数据范围:
50%的数据N,M<=1000
100%的数据N,M<=20000
初步分析枚举

F(i)为以Ai结尾长度不超过M的最大子序和
F(i)=max{工1AIk=l..m}
j
j=i-k+1
对于每个F(i),从1到m枚举k的值,完成Aj的累加和取最大值。
该算法的时间复杂度为O(n2)
简化方程
令s(i)八iA
j
j=i
F(i)二max{JAIk二1・.m}
j
j=i-k+1
=max{S(i)一S(i-k)Ik=1・.m}
=S(i)—min{S(i—k)Ik=1・.m}
3、holiday・pas/c/cpp
Description
经过几个月辛勤的工作,

最近更新

2025年四川文化传媒职业学院单招职业倾向性考.. 73页

2025年成都银杏酒店管理学院单招职业技能测试.. 72页

2025年四川文轩职业学院单招职业技能测试题库.. 74页

2025年扬州工业职业技术学院单招职业技能测试.. 75页

2025年扬州市职业大学单招职业倾向性考试题库.. 74页

2025年四川电子机械职业技术学院单招职业倾向.. 73页

2025年承德护理职业学院单招职业倾向性考试题.. 71页

北钢院项目技术方案 26页

2025年抚顺职业技术学院单招职业倾向性测试题.. 72页

2025年抚顺职业技术学院单招职业适应性考试题.. 73页

2025年四川长江职业学院单招职业倾向性考试题.. 75页

2025年攀枝花攀西职业学院单招职业技能测试题.. 73页

2025年大同煤炭职业技术学院单招职业倾向性测.. 73页

2025年大连汽车职业技术学院单招综合素质考试.. 75页

2025年大连职业技术学院单招职业倾向性考试题.. 74页

2025年大连航运职业技术学院单招职业倾向性考.. 74页

2018-2019中学班级工作计划与2018-2019六年级.. 7页

人教版八年级物理下册期末复习题含答案 4页

2025年天津交通职业学院单招职业技能测试题库.. 74页

2025年天津城市职业学院单招职业技能测试题库.. 74页

各种常见引流管的护理-PPT 36页

伊利乳业纯牛奶工艺流程图 4页

水利工程中隧洞固结灌浆施工技术分析 32页

牌匾施工方案 26页

牌匾规范施工方案 10页

年产15万吨环己醇工艺设计【完整版】 37页

粗盐提纯除去可溶性杂质课件 19页

西田龙雄:关于十六世纪西康省藏语天全方言—.. 92页

起重机试运转检验记录 1页

仁焕法师--乘佛本愿之妙用(如何请法、用法)第.. 37页