动态规划状态转移方程课件

动态规划（提高组）绍兴柯桥中学吴建锋部分背包问题N个物品，每个物品有总价值a[i]和体积v[i]，背包的总体积是W，每个物品可以部分拿取，问最大可以获得价值。部分背包问题1、获取价值最大，就是在装满背包的前提下获得总价值最大2、要使总价值最大，显然要使单位体积的价值含有量最大3、因为物品可以一份份取，导致每个物品装入时的性价比是固定的（就是a[i]/v[i]）01背包问题N个物品每个有价值a[i]和体积v[i]，但每个物品不能分割（要么全部取，要么不取），求最大的背包所含的价值。01背包问题1、如果不管哪个物品装入，都能恰好装满背包，那么问题就是“背包单位体积所含价值最大”2、可能出现的情况是某些性价比较高的物品装入后导致其他性价比较低物品不能装入，导致背包体积被浪费。所以不能再用贪心了3、只能用DP解决01背包问题Fori:=1tondoforj:=0towdobeginf[I,j]:=f[i-1,j];if(j>=v[i])and(f[i-1,j-v[i]]+a[i]>f[I,j])thenf[I,j]:=f[i-1,j-v[i]]+a[i]>f[I,j]end;枚举阶段（所有物品）枚举状态（当前背包被占用体积）当前物品不装入背包的最大总价值就是前i-1个物品装入背包的最大值。把当前背包不装入和装入进行比较，哪个更大，难度是子状态的转移，上一个子状态就是j-v[i]，因为v[i]装入前，背包被占用体积就是j-v[i]。可以和tom问题中的状态转移联系起来，当前任务完成的前一个子状态就是当前时刻减去当前任务占用时间01背包的又一个程序Fori:=1tondoBeginforj:=0tov[i]-1dof[I,j]:=f[i-1],j];forj:=v[i]towdobeginiff[i-1,j-v[i]]+a[i]>f[I,j]thenf[I,j]:=f[i-1,j-v[i]]+a[i]>f[I,j]end;End;扩展01背包问题N种物品，每种有无穷多个，价值为a[i]，单个体积为v[i]，装入总体积为W的背包，求最大价值和。扩展01背包问题1、k=0时表示物品i不取，则对应的f[I,j]=f[i-1,j]2、k>0时，表示物品i装入了被占用j体积的背包中有k个，这个决策对应的上个可能的子状态是：背包被占用体积是j-v[i]（可以不管当前装入的物品i已经装入几个了）。对应的最优解就是：f[I,j]:=f[I,j-v[i]]+a[i]另一种形式的程序Fori:=1tondoforj:=1tov[i]-1dof[I,j]:=f[i-1,j];forj:=v[i]towdoiff[i-1,j]>f[I,j-v[i]]+a[i]thenf[I,j]:=f[i-1,j]elsef[I,j]:=f[I,j-v[i]]+a[i]；经典问题：矩阵连乘有n个矩阵，计算他们连乘的最少乘法次数。输入第一行为一个整数n，表示参加连乘的矩阵的个数，下面n行，依次给出各个矩阵的行数和列数规模。输出最少的乘法次数（连乘目标是只有一个矩阵）。输入和输出输入：315520201输出：105前期分析1、什么是矩阵乘法2、乘法次数的统计原理算法分析1、阶段。分相邻二个矩阵相乘、相邻三个相乘、……n个矩阵相乘来划分阶段。2、状态。连乘矩阵的起始和终止编号。3、决策。在i和j矩阵之间如何组合。首先是两两相乘Fori:=1ton-1do F[i,i+1]:=a[i].x*a[i].y*a[i+1].y;然后是更大规模的连乘Forlen:=3tondo Fori:=1ton-len+1doBeginj:=i+len-1;F[i,j]:=maxlongint;Fork:=itoj-1doIfF[i,j]>F[i,k]+F[k+1,j]+a[i].x*a[k].y*a[j].yThenBeginF[i,j]:=F[i,k]+F[k+1,j]+a[i].x*a[k].y*a[j].y;End;End；输入输出stone.in305205010301544514413stone.out88问题分析1、有些选手会陷入二种错误的贪心算法中2、为什么可用动态规划3、3个要素的分析（1）阶段（2）状态（3）决策核心程序代码fillchar(f,sizeof(f),0);fori:=1tondoforj:=1towdobeginf[I,j]:=f[i-1,j];if(w[i]<=w)and(f[I,j]<f[i-1,j-w[i]]+p[i])thenf[I,j]:=f[i-1,j-w[i]]+p[i];end;write(f[n,w]);joy的工具箱Joy是一位非常出色的汽车维修工，而且他的创业能力也很强，这不，最近他成立了自己的汽车维修110公司，一旦汽车在半途抛锚，只要一个电话，joy就会立刻带着他的工具箱赶到事故地点，为驾驶员朋友维修汽车，由于抢修及时以及维修技术高，汽车维修110公司的生意越来越红火。但joy是一个追求无止境的人，在生意越做越大的同时，他又动开了新脑筋。他发现无论维修工具箱买得如何大，肯定不能把他公司里所有的维修工具装进去，100％的故障排除率不仅需要精湛的维修技术，如何选择并把最为合适的维修工具装入工具箱，并把工具箱带到故障现场，也是一个非常重要的技巧。由于工具众多，joy无法根据驾驶员报告的故障现象确定最为合适的一些工具，作为朋友的你决定通过程序来帮助joy选择最为合适的工具转入到工具箱中。

当然，joy会事先告诉你一些必要的信息。比如，他的每个工具都是不同的，工具箱的总体积，joy还会告诉你他根据故障特点给每个工具合适程度的效率分数，你的程序必须能确定哪些工具被装入工具箱，并输出总的最大效率分。输入和输出joy.in23511209191015714815joy.out39关键要素分析1、阶段2、状态3、决策分析状态转移方程F[I,j]表示前i个工具选择部分装入占用容量为j的工具箱中的最大效率分：f[i,j]:=max{f[i-1,j-v1[i]]+p[i]|}核心程序段fillchar(f,sizeof(f),0);fori:=1tondoforj:=1tovdobeginf[i,j]:=f[i-1,j];if(v1[i]<=j)and(f[i,j]<f[i-1,j-v1[i]]+p[i])thenf[i,j]:=f[i-1,j-v1[i]]+p[i];end;write(f[n,v]);经典问题的应用：石子归并在一个操场上摆放着一排n（n≤20）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分。模型分析1、任意两堆石子的合并就是两个矩阵的相乘。2、更为简单的是，这里只是石子数的累加。状态转移分析1、用a[i]表示第i堆石子的数量2、f[I,j]表示第i堆到第j堆合并为一堆的最小分数3、f[I,j]=min{f[I,k]+f[k+1,j]+sigma(a[t]|i<=t<=j)|i<=k<j}4、初始化时必须是：f[I,i]：＝maxint;f[I,i]:=0总体算法分析1、先用循环求得所有的f[I,i+1]，1<=i<n2、以合并包含的原始石子堆的数量为阶段（从3到n），进行动态规划求解。3、输出f[1,n]。TOM的烦恼Tom是一个非常有创业精神的人，由于大学学的是汽车制造专业，所以毕业后他用有限的资金开了一家汽车零件加工厂，专门为汽车制造商制造零件。由于资金有限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家汽车制造商需要他加工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同厂家对于不同零件的加工时间要求不同（有些加工时间要求甚至是冲突的，但开始和结束时间相同不算冲突）。Tom当然希望能把所有的零件都加工完，以得到更多的加工费，但当一些零件的加工时间要求有冲突时，在某个时间内他只能选择某种零件加工（因为他只有一台机器），为了赚得尽量多的加工费，Tom不知如何进行取舍，现在请你帮Tom设计一个程序，合理选择部分（或全部）零件进行加工，使得得到最大的加工费。输入文件input.txt的第一行是一个整数n（不超过100000），表示共有n个零件须加工。接下来的n行中，每行有3个整数，分别表示每个零件加工的时间要求，第一个表示开始时间，第二个表示该零件加工的结束时间，第三个表示加工该零件可以得到的加工费。输出文件output.txt只包含一个整数，表示Tom可以得到的最大加工费。结果输出到文件output.txt输入输出样例【输入样例】3131046202525【输出样例】30算法分析用sum[i]表示到达时刻i时所能得到的最大收益，用a[j,1]表示任务j的开始时间，a[j,2]表示任务j的结束时刻，b[j]表示任务j完成所得的加工费。sum[i]=max{sum[k]]+b[j]|1<=k<=a[j,1]<a[j,2]<＝i}123456789101112131415723465174421819核心程序如下sum[0]:=0;

fori:=1tomdo

begin

max:=0;

forj:=1tondo

ifa[j,2]<=i

thenifmax<sum[a[j,1]]+b[j]

thenmax:=sum[a[j,1]]+b[j];

sum[i]:=max;

end;

writeln(sum[m]);算法优化1、原算法的时间复杂度是？2、是否有优化的余地？3、排除重复是本题一个优化的方向重复处理的分析1、在某个阶段的时刻i枚举时，如果没有新的任务刚好结束，当前时刻对应的最优解是不会改变的，所以也不必去枚举已经产生的子问题，然后来重复判断当前问题的最优解。2、每到达一个新时刻，当前时刻如果有新任务结束，也不必从头到尾重新枚举所有此前结束的加工任务，而只需从上次结束的加工任务后开始枚举即可。考虑到这点，我们需要实现作个预处理，即按照加工任务结束时刻的先后对输入的所有任务进行排序。排除重复1、每到一个新的时刻i，最优解ans[i]可分哪些情况来分别产生？有新任务结束和没有新任务结束两种情况。2、如果有新任务结束，如何来判断是哪些并分并处理？预处理时把每个时刻结束的任务编号保存起来。优化后的核心算法部分对所有任务按照结束时间进行从小到大排序；计算最后一个任务的结束时刻m；ans[0]:=0;fori:=1tomdobeginans[i]:=ans[i-1];if当前有任务j刚好结束(j可能不止一个)thenbeginifans[i]<ans[a[j,1]]+b[j]thenans[i]:=ans[a[j,1]]+b[j];end;end;write(ans(m));办公室主任艾薇作为办公室的主任已经很长时间了，作为一个部门主管，她不但要负责全部门的工作安排、人员调动等组织工作，而且为了身先士卒，她总给下属的感觉是“上司一刻不停地在工作！”，所以这些下属们觉得头儿这么卖力，大家也都很卖力、负责地工作，因此，近几年来，艾薇负责的部门连续受到上级的表彰。看着艾薇这么一刻不停地工作，大家有时不免要劝阻她“要注意休息，身体是革命最大的本钱！”。

但艾薇自己却知道，虽然她给人的感觉在“一刻不停地工作”，但实际上她却在巧妙、科学地“偷懒”。因为她十分清楚，作为主管，她绝对不能象下属那样整天埋头于琐碎、具体的工作，她必须有足够的时间来统配、组织大家合作地把部门工作搞好，而且这是一个优秀主管的首要工作，但她也总不能因为这个原因而跟大家说“我要负责其他工作，所有这些具体事务都你们做吧”。于是，她聪敏地想到了一个“冠冕堂皇”的“偷懒”的工作安排方法，这个安排方案看起来会使人觉得艾薇确实太身先士卒了，因为如果在某个时刻，某项工作必须开始做了，而恰好艾薇手头现在没有具体工作在做，那么这项工作必须由艾薇来完成；当然，如果现在艾薇正在做一项未完成的具体工作，那么这项工作就由其他下属完成；作为主管，有时当一批工作需要在某个时刻同时开始时，艾薇负责分配这些具体工作由谁来完成，当然喽，艾薇会在此时巧妙地保证自己不露痕迹地“偷懒”（选择对自己有利的具体工作来完成）。在这种策略下，艾薇总能在分配具体工作时，分配给自己恰当的具体工作，使得自己在一天中有最多的空余时间，她就可以利用这些空余时间，很好地策划、安排、组织本部门的一些组织管理工作了。现在告诉你某天该部门所有必须完成的具体工作的一些信息（每个具体工作以开始时间的先后顺序给出），编程计算艾薇最多能获得的空余时间总数。我们假定艾薇从上班时刻到下班时刻之间都不会离开办公室，她都会在工作岗位上。输入文件director.in第一行包含二个用用空格分隔的整数n和k（1<=n<=10000,1<=k<=10000），n表示艾薇一天总的上班时间，单位分分钟，k表示该部门必须在当天完成的具体工作总数。接下来共有k行，每行有二个用空格分隔的整数s和t，表示该具体工作从第s分钟的开头必须开始，持续时间分t分钟，其中1<=s<=n，1<=s+t-1<=n。如果某具体工作从s分钟开始，持续时间为t分钟，则该具体工作将在第s+t-1分钟的末尾结束。输出文件director.out只有一行一个整数，表示艾薇可能获得的最大空余时间。输入和输出样例director.in15612164118581115director.out4问题分析用ans[i]表示从i分钟开始到最后一分钟结束时的最优解（获得了最大空余时间）05810141618201234算法分析1、类似于上题，对所有工作按照开始时刻进行排序2、类似于上题，枚举到一个新时刻，判断是否刚好有新工作需要开始状态转移方程ifs[j]<>Ithenans[i]:=ans[i+1]+1{没有当前时刻开始的任务，累加前移的时间间隔1}elseans[i]:=max{ans[i+t[j]]|s[j]=i}{当前有多个任务可选，则选择一个能保证当前规模问题有最优解的子问题}核心算法j:=k;{从排序后的最后一个任务开始往前穷举}fori:=ndownto1do{从后往前穷举阶段}beginans[i]:=0;{为下面求最大值作准备}ifs[j]<>Ithenans[i]:=ans[i+1]+1{当前时刻没有刚开始任务，则空余时间为上1分钟的空余加上前移的空余时间1分钟。这个也是子状态之一}elsewhiles[j]=Ido{穷举所有子状态。刚好有任务从当前时刻开始的子状态}beginifans[i+t[j]]>ans[i]thenans[i]:=ans[i+t[j]];{枚举所有状态转移结果，比较求得最优解}j:=j-1;{继续穷举按照开始时间先后排序的任务往前枚举任务}end;end;核心程序段fori:=ndownto1dobeginans[i]:=0;ifs[j]<>ithenans[i]:=ans[i+1]+1elsewhiles[j]=idobeginifans[i+t[j]]>ans[i]thenans[i]:=ans[i+t[j]];j:=j-1;end;end;数据结构和输入constmaxn=10000;maxk=10000;varans:array[1..maxn+1]ofinteger;s:array[0..maxk]ofinteger;t:array[1..maxk]ofinteger;n,k,i,j:integer;fin,fou:text;beginassign(fin,'director.in');reset(fin);assign(fou,'director.out');readln(fin,n,k);fori:=1tokdoreadln(fin,s[i],t[i]);close(fin);j:=k;ans[n+1]:=0;最后输出rewrite(fou);writeln(fou,ans[1]);close(fou);超市购物约翰手拿购物清单通过超市的走廊，走廊的一边全部是各个承包商的购物铺，各个商铺提供的物品可能相同也可能不同，现在约翰希望严格按照购物清单上的顺序购买所有的物品，并且力求总的费用最少。问题是约翰只能通过走廊一次并不能走回头路，判断约翰是否能购买到清单上所列的物品，如果可以，输出最少费用，如果不行，则输出“Impossible”。输入数据第一行是二个整数m和n，分别表示清单上所有物品的项目和走廊上包含的商铺数