day7动态规划1-荆晓虹
动态规划一
江苏省丹阳高级中学 荆晓虹2014.7 赣榆
从一个例子谈起
问题描述：
大J摆出一排长短不一的筷子，筷子的长度是一个正整数序列b1，b2，b3，…，bn，她问小L，拿掉最少数量的筷子，就可以使剩下的筷子从矮到高“排好队”了呢？输出留下的筷子队形的长度，即形成高矮排队的筷子的根数。
问题输入：
一行多个用空格隔开的整数，表示每根筷子的长度。
问题输出：
一个整数，表示最终队形里筷子的根数。
输入样例：
13 7 9 16 38 24 37 18
输出样例：
5
数据限制：
0<n<=100
递归地定义最优解的值b[1]=1, b[2]=1, b[3]=1 ,...... i-1
b[i]=max{b[j] | a[i]>=a[j]} + 1 j=1
完整的动态规划求解的程序program ex1;
var i,j,n,len:integer;
a,b:array[1..100] of integer; begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
b[i]:=1;
end;
☆如何运用动态规划
for i:=2 to n do
begin
len:=0;
for j:=1 to i-1 do
if (a[i]>=a[j]) and (b[j]>len) then len:=b[j]; if len>0 then b[i]:=len+1;
end;
…
构建最优解
len:=1;
for j:=2 to n do
if b[j]>len then len:=b[j]; writeln('maxlen=',len);end.
小结
?动态规划是一种算法策略, 它采用了两个主要的设计方法:
–表格化 - 利用数组存储中间计算环节
–自底向上 - 从最底层子问题开始, 逐步上升计算, 最后得到问题的解?动态规划主要适用于一类所谓的“最优化”问题, 即求最大(或最小)值. 当
分析问题的性质, 满足如下二点时, 就可采用动态规划策略求解:–最优子结构 - 问题的一个最优解中包含着子问题的一个最优解.
–重叠子问题 – 求解问题的解时要反复计算若干个子问题. 同理, 求解各个子问题时又要反复计算若干子子问题, 这些子子问题可能是新产生的, 也可能是重复产生的.
☆什么是动态规划
动态规划（Dynamic Programming）
动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年，美国数学家R.Bellman提出了解决这类问题的“最优化原则”，1957年发表了他的名著《动态规划》，该书是动态规划方面的第一本著作。动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用，取得了显著的效果。
动态规划成为了信息学竞赛中必不可少的一个重要方法，几乎在所有的国内和国际信息学竞赛中，都至少有一道动态规划的题目。所以，掌握好动态规划，是非常重要的。
☆什么是动态规划
动态规划中的相关概念：
1、阶段
用动态规划求解一个问题时，需要将问题的全过程恰当地划分成若干个相互联系的阶段，以便按一定的次序去求解。阶段的划分一般是根据时间和空间的自然特征来定的，一般要便于把问题转化成多阶段决策的过程。
2、状态
状态表示的是事物某一阶段的性质，状态通过一个变量来描述，这个变量称为状态变量。各个状态之间是可以相互转换的。
☆什么是动态规划
3、决策
对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策，在每一个阶段中都需要有一次决策。一次决策就会从一个阶段进入另一个阶段，状态也就发生了转移。
4、策略和最优策略
所有阶段按照约定的决策方法，依次排列构成问题的求解全过程。这些决策的总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。
☆什么是动态规划
更多内容请访问久久建筑网
5、状态转移方程
前一阶段的终点就是后一阶段的起点，这种关系描述了由K阶段到K+1阶段状态的演变规律，是关于两个相邻阶段状态的方程，称为状态转移方程，是动态规划的核心。
算法模式图动态规划
多个规划(决策)当前最优决策
当前非最优决策
规划方向
初始
阶段当前
阶段i目标阶段
i向着目标阶段不断改变(动态)
当前阶段的决策仅受前一阶段决策的影响,并决定下一个阶段的决策求得的一个最优解
如何运用动态规划
例2：题目名：K双筷子（*.in/out/pas/cpp）
问题描述：
大J有很多根筷子，因为筷子的长度不一，很难判断出哪两根是一双的。这天，家里来了K个客人，大J留下他们吃晚饭。加上小L和他的爸爸妈妈，共K+3个人。每人需要用一双筷子。大J只好清理了一下筷子，共N根，长度为T1，T2，T3，…，TN。现在她想用这些筷子组合成K+3双，使每双的筷子长度差的平方和最小。小L请你帮忙。
问题输入：
输入文件中共两行，第一行为两个用空格隔开的整数N，K。
第二行共有N个用空格隔开的整数，为Ti每个整数为1～50之间的数。
问题输出：
输出文件中仅一行。如果凑不齐K+3双，输出-1，否则输出长度差平方和的最小值。
输入样例：
10 11 1 2 3 3 3 4 6 10 20
输出样例：
5
样例说明：
第一双 1 1
第二双 2 3
第三双 3 3
第四双 4 6
(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5。
数据限制：
1<=N<=100，0<K<50
解结构
数据结构：
设定有n个元素的一维数组整型数组a和有n2个元素的二维数组整型数组opt；
a[i]表示第i个数的数值本身；
opt[i，j]表示前i根筷子配好j双筷子时的最小长度差的平方和的大小；
递归地定义最优解的值opt赋初值（最大值）
Opt[0,0]=0
opt[i,j]=min{opt[i-1,j]
opt[i-2,j-1]+(a[i]-a[i-1])^2} 1<=i<=n,1<=j<=k+3
自底向上计算最优解的值求解过程：
opt[1,1]=
…
Opt[2,1]=
…
Opt[3,1]= opt[3,2]=
完整的动态规划求解的程序var
opt : array[0..maxn,0..53] of longint;
a : array[1..100] of integer;
n,k : integer;
i,j : integer;
procedure sort;
var
i,j,temp : integer;
begin
for i := 1 to n-1 do
for j := i+1 to n do
if (a[i]>a[j]) then
begin temp := a[i];
a[i] := a[j];
a[j] := temp;
end;
end;
readln(n,k);
for i := 1 to n do read(a[i]);
if (n<2*k+6) then begin
writeln(-1);
close(input); close(output); halt;
end;
sort;
fillchar(opt,sizeof(opt),$7F);
opt[0,0] := 0;
for i := 1 to n do
for j := 1 to k+3 do
if (i>=2*j) then
begin
if (opt[i-1,j]<opt[i,j]) then opt[i,j] := opt[i-1,j]; if (opt[i-2,j-1]+sqr(a[i]-a[i-1])<opt[i,j]) then opt[i,j] := opt[i-2,j-1]+sqr(a[i]-a[i-1]); end;
writeln(opt[n,k+3]);
end.
如何运用动态规划
题目名：包装筷子（chop.in/out/pas/cpp）
问题描述：
大J收集的N根的不同的筷子，她对每根筷子都根据喜爱程度标上一个整数，称为喜爱度。这天她想带一部分最喜爱的筷子送给好朋友。她找来一个盒子，想把筷子装起来，为了在路上颠簸不会摩擦碰伤筷子，她找来一包棉花，用来填塞筷子之余的空隙。盒子里去掉棉花占据位置后，总容量还有Vmax，她想选择一些筷子装进盒子，使得盒子里装的筷子总喜爱度是所有装载方案中最大的。
问题输入：
第一行为两个整数，依次表示盒子的可用容量V和所有的筷子数量N。 下面共有n行，每行有两个用空格分隔的整数，依次表示某根筷子的体积和喜爱度。
问题输出：
输出仅一行为一个整数，表示盒子最终所装筷子的最大总喜爱度。
如何运用动态规划输入样例：
10 52 62 36 55 44 6
输出样例：
15
数据限制：
1<=V<=1000，1<=N<=100
对于30%的数据，满足：N<=10；对于100%的数据，满足：N<=100。
辽公网安备 21020302000024号工信部备案号: 辽ICP备15011726号-5
