下载文档原格式
动态规划练习题USACO 2.2 Subset Sums题目如下：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。
举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：and {1,2}这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:{1,6,7} and {2,3,4,5} {注1+6+7=2+3+4+5}{2,5,7} and {1,3,4,6}{3,4,7} and {1,2,5,6}{1,2,4,7} and {3,5,6}给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。
程序不能预存结果直接输出。
PROGRAM NAME: subsetINPUT FORMAT输入文件只有一行，且只有一个整数NSAMPLE INPUT (file subset.in)7OUTPUT FORMAT输出划分方案总数，如果不存在则输出0。
SAMPLE OUTPUT (file subset.out)4参考程序如下：#include <fstream>using namespace std;const unsigned int MAX_SUM = 1024;int n;unsigned long long int dyn[MAX_SUM];ifstream fin ("subset.in");ofstream fout ("subset.out");int main() {fin >> n;fin.close();int s = n*(n+1);if (s % 4) {fout << 0 << endl;fout.close ();return ;}s /= 4;int i, j;dyn [0] = 1;for (i = 1; i <= n; i++)for (j = s; j >= i; j--)dyn[j] += dyn[j-i];fout << (dyn[s]/2) << endl;fout.close();return 0;}USACO 2.3 Longest Prefix题目如下：在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。
附表5：考试课程： 班级： 姓名： 学号：------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------、⑴ 证明:令F （N ）=O(f)，则存在自然数N1、C1，使得对任意的自然数N 1N ≥，有: F（N));(1N f C ≤……………………………。
.（2分）同理可令G （N ）=O （g ）， 则存在自然数N2、C2，使得对任意的自然数N 2N ≥,有: G（N));(2N g C ≤ ……………………………。
（3分）令 C3=max{C1，C2}，N3=max{N1，N2｝,则对所有的N 3N ≥，有: F(N));(3)(1N f C N f C ≤≤G （N ）);(3)(2N g C N g C ≤≤ ……………………………..(5分） 故有：O(f ）+O(g)=F(N)+G （N))())()((3)(3)(3g f O N g N f C N g C N f C +=+=+≤ 因此有:O （f ）+O(g)=O(f+g) …………………………….。
（7分）⑵ 解：① 因为：;01033)103(lim 222=+-+∞→nn n n n n 由渐近表达式的定义易知: 103322+n n 是的渐近表达式。
……………………………。
.(3分） ② 因为：;0/12121)/121(lim=+-+∞→nn n 由渐近表达式的定义易知：21是21+1/n 的渐近表达式。
…………………………….。
（6分）2、解：经分析结论为:（1）);5(log log 2+=n n θ…………………………。
2008年城市规划师考试《规划原理》真题回忆版单选1.GNP -----国民生产总值2.京都议定书-------温室效应3.不属于总规强制性规定的是-----地下空间4.集中集约集聚-------B集中是人口的集中集约是产业的集约集聚是高效利用5.基尼系数------正确答案:居民收入分配不平均(答错!!!)6.城镇化-------城市生活方式向农村的扩散7.不包括------暂住三个月的人口8.区域对城市最大的影响-------城市性质和规模9.雅典卫城的核心-------广场(曾经在广场与神庙之间徘徊的好久!!!)10.马丘比丘宪章--------人与人的交往11.巴黎改建---------A.政府参与组织的城市更新(没找到道路改造的选项!!!)12.可识别性--------A.场所有清晰的意象和易于认识的熟悉13.不正确的是--------C.元大都皇城居中14.城市道路交通调查的目的--------分析交通存在问题的原因15.城市综合交通----------存在于城市中与城市有关的各种交通形式16.城市交通政策----------B.技术政策经济政策管理政策17.不正确的是---------城市道路高架(貌似也选错!!!)18.道路红线的定义-------道路用地与两侧建筑用地分界线的距离19.不属于第二产业的是----------正确答案:仓储物流业(MMD交卷前改成了采掘业!!!)20.历史文化错误的是---------重建部分历史建筑21.居住区划分原则不包括---------A.城乡统筹(完全不确定,但是感觉居住区跟城乡应该没太大联系吧!!!)22.电力规划不正确的是--------D要坚持....的战略(C是每个阶段都要预测供电负荷,偶选的D,应该错!!!)23.燃气规划在详规阶段不包括-------选择气源种类24.反映社会指标--------貌似自然增长率吧(可是我又改成了三废处理率,完全不搭边嘛!!!)25.竖向规划不包括--------C.改造地形26.近期规划正确的是--------A.城市规划的组成部分(不确定,书上又说是项计划,倒!!!)27.还是近期规划的-------宏观调控作用28.以下错误的是-------D.所有城市规划都要考虑中低收入人群的居住(题目记不起来了,前三个选项也忘!!!)29.修规的内容不包括-------绿化率.容积率等规定30.还是修规的---------分图图则31.规划条件的依据---------控规32.总规调查内容不包括---------D.用地权属(在规模和权属中艰难抉择!!!)33.反应地块开发强度---------容积率34.总规成果不包括--------远期规划图35.不属于法定规划的是---------B.......的修规(AC肯定是,莫非村庄规划不是!!!)36.正确的是--------C.所有镇都要依据镇规划标准(OMG又感觉好像不对哦!!!)37.城市规划的特点不包括-------战略性38.地景--------正确答案:岛屿礁(我选的沼泽滩涂!!!)39.关于控规不正确的是---------必须先修改总规40.非公共部门--------也可以实施城市规划41.不正确的是--------A.以划拨方式首先要申请建设用地规划许可证42.盆地城市主要受什么影响---------A静风频率43.不正确的是---------A.控规属于法规体系44.控规的强制性内容不包括---------后退距离45.表格题--------R1(试后想想好像应该是R2!!!)46.不正确的是----------A油库位于交通枢纽47.城市水源优先----------中水回用(不确定!!!)48.工业选址不正确的是---------B.危险性工业不靠近干线公路(貌似应该选地形平坦!!!)49.不对居住区人均建设有影响的是--------D绿化覆盖率50.离散程度分析--------标准差51.影响最小的是--------森林资源52.禁建区--------基本农田53.城市用水分为---------生活工业消防市政54.公交站---------50%55.分类正确的是----------C.公交保养场属于市政用地56.地下空间规划错误的是----------B以总规为依据(错!此项正确!书上原话!!!)57.可选择性活动---------喝咖啡观看路人58.高压走廊----------D.应避开规划的中心区59.不正确的是----------C.可持续发展的核心是保护生态环境60.华东小城市的住宅日照----------正确答案:大寒日3小时(OMG,偶选的寒2!!!)61.全国城镇体系规划的内容不包括---------各县城的分布62.省域城镇体系规划的内容不包括---------优先发展区.....(完全错误,但偶记不得剩下的答案了!!!)63.不正确的是---------人均用地不超过10064.规划总平与建筑设计的不同--------编制单位的资质(后来想想没那么简单,貌似应该选D群体单栋!!!)65.不属于消防设施的是----------消防通道66.历史文化名称----------名城街区文保单位67,雅典宪章不正确的是-----------与区域的联系68.居住区道路错误的是-----------B.独立的停车楼多选(没有特别确定的,将就着混个脸熟~~~)1.城镇布局中属于集中形态的是--------放射,星座(选项还有同心圆组团散点!!!)2.属于行政建制的是---------CE3.区域与城市的关系---------DE4.道路系统规划的要求------------骨架通道管线景观5.城镇体系的特性---------关联整体层次,还有一个忘了6.高速公路连接的正确方式---------压根没看答案7.居住小区以10000__15000是因为----------道路间距.配建设施门槛8.绿地旅计算不包括---------郊野公园,水源保护地9.城关镇控规正确的是---------ABCE除了要审查10.不应管线共沟的是----------胡选的AB11.风景名胜区划分为----------国家和省级12.城市规划的作用----------BCD,有配置空间资源嘛?13.可持续发展采用的措施----------忘选了公众参与,倒!14.多选第一题--------AE难道C只有大城市才有多核心结构也是对的嘛?。
题三加分二叉树（2003）【问题描述】设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。
每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。
不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。
要求输出；（1）tree的最高加分（2）tree的前序遍历【输入格式】第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
【输出格式】第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
【输入样例】55 7 1 2 10【输出样例】1453 1 24 5[分析]很显然，本题适合用动态规划来解。
如果用数组value[i,j]表示从节点i到节点j 所组成的二叉树的最大加分，则动态方程可以表示如下：value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j], value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j ,j], value[j,j]+value[i,j-1]}题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点i到节点j 所组成的最大加分二叉树的根节点，用数组root[i,j]表示[PASCAL源程序]{$N+}program NOIP2003_3_Tree;constmaxn=30;vari,j,n,d:byte;a:array[1..maxn]of byte;value:array[1..maxn,1..maxn]of comp;root:array[1..maxn,1..maxn]of byte;s,temp:comp;f1,f2:text;fn1,fn2,fileNo:string;procedure preorder(p1,p2:byte);{按前序遍历输出最大加分二叉树}beginif p2>=p1 then beginwrite(f2,root[p1,p2],' ');preorder(p1,root[p1,p2]-1);preorder(root[p1,p2]+1,p2);end;end;beginwrite('Input fileNo:');readln(fileNo);fn1:='tree.in'+fileNo;fn2:='tree.ou'+fileNo;assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2);readln(f1,n);for i:=1 to n do read(f1,a[i]);close(f1);fillchar(value,sizeof(value),0);for i:=1 to n do beginvalue[i,i]:=a[i];{计算单个节点构成的二叉树的加分}root[i,i]:=i;{记录单个节点构成的二叉树的根节点}end;for i:=1 to n-1 do beginvalue[i,i+1]:=a[i]+a[i+1];{计算相邻两个节点构成的二叉树的最大加分}root[i,i+1]:=i;{记录相邻两个节点构成的二叉树的根节点；需要说明的是，两个节点构成的二叉树，其根节点可以是其中的任何一个；这里选编号小的为根节点，则编号大的为其右子树；若选编号大的为根节点，则编号小的为其左子树；因此，最后输出的前序遍历结果会有部分不同，但同样是正确的。
填空题动态规划算法的基本要素为：最优子结构性质与重叠子问题性质1)算法分析中，记号O表示渐进上界，记号Ω表示渐进下界，记号Θ表示紧渐进界。
2)回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
3)分支限界法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间树。
所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。
所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。
回溯法是指（具有限界函数的深度优先生成法）。
回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。
4)二分搜索算法是利用分治策略实现的算法。
5)衡量一个算法好坏的标准是时间复杂度低6)最长公共子序列算法利用的算法是动态规划法7)Strassen矩阵乘法是利用分治策略实现的算法8)回溯法搜索状态空间树是按照深度优先遍历的顺序。
9)算法中通常以自底向下的方式求解最优解的是动态规划法10)背包问题的贪心算法所需的计算时间为O（nlogn）11)0-1背包问题的回溯算法所需的计算时间为O（n2n）12)用动态规划算法解决最大字段和问题，其时间复杂性为n13)一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性，确定性，可行性，输入，输出。
1.算法的复杂性有时间复杂性和空间复杂性之分。
2、程序是算法用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。
4.矩阵连乘问题的算法可由动态规划设计实现。
6、算法是指解决问题的一种方法或一个过程。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。
8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
9、以深度优先方式系统搜索问题解的算法称为回溯法。
10、数值概率算法常用于数值问题的求解。
动态规划复习题在计算机科学和数学领域中，动态规划是一种非常重要的算法思想和解题策略。
它常常被用于解决那些具有重叠子问题和最优子结构性质的问题，能够有效地降低计算复杂度，提高算法的效率。
动态规划的核心思想是将一个复杂的问题分解成若干个子问题，并通过保存子问题的解来避免重复计算，从而逐步求解出原问题的最优解。
这种方法的关键在于找出问题的最优子结构和状态转移方程。
让我们通过一个经典的例子来理解动态规划的基本概念。
假设有一个楼梯，我们需要从楼梯的底部走到顶部。
每次可以向上走 1 级或者 2 级台阶。
那么，请问走到第 n 级台阶共有多少种不同的走法？我们可以用动态规划的方法来解决这个问题。
首先，定义一个数组dp，其中 dpi 表示走到第 i 级台阶的不同走法数量。
对于第 1 级台阶，只有 1 种走法，即直接走上去，所以 dp1 ＝ 1。
对于第 2 级台阶，可以一次走 2 级，也可以分两次每次走 1 级，所以 dp2 ＝ 2。
对于第 i 级台阶（i ＞ 2），它可以从第 i 1 级台阶走 1 级到达，也可以从第 i 2 级台阶走 2 级到达。
所以，走到第 i 级台阶的走法数量等于走到第 i 1 级台阶的走法数量加上走到第 i 2 级台阶的走法数量，即dpi ＝ dpi 1 ＋ dpi 2。
通过这种方式，我们可以从第 1 级和第 2 级台阶的基础情况出发，逐步计算出 dpn，即走到第 n 级台阶的不同走法数量。
另一个常见的动态规划问题是背包问题。
假设有一个背包，它的容量为 C，有 n 个物品，每个物品有自己的重量 wi和价值 vi。
我们需要选择一些物品放入背包，使得背包中物品的总价值最大。
同样地，我们可以定义一个二维数组 dp，其中 dpij 表示在前 i 个物品中，背包容量为 j 时能够获得的最大价值。
对于第 1 个物品，如果背包容量足够容纳它，那么 dp1j ＝ v1（j ＞＝ w1），否则 dp1j ＝ 0。
第八章动态规划动态规划模型和求解方法(1)阶段．(2)状态．描述过程在第k阶段状态的变量，称为状态变量，用s k表示．s k取值的全体记作S k，称作第k阶段的状态集合．状态的定义在动态规划中往往是最重要的概念．它必须具备3个特性：①描述性．各阶段状态的演变能描述决策过程．②无后效性．如果第k阶段的状态给定，则在这阶段以后过程的发展不受这阶段以前各个阶段状态的影响．也就是说，过程未来的发展，只与过程的现在状态有关，而与过程的过去状态无关．③阶段状态变量的取值，直接或间接是可知的，也就是说，第k阶段的状态集合S k是给定的．(3)决策．当第k阶段的状态s k给定后，从该状态演变为第k+1阶段状态时所作的选择称为决策．描述决策的变量称为决策变量，用x k(s k)表示，简记为x k．x k(s k)取值的全体记为D k(s k)，称为第k阶段的决策集合，s k取值不同，相应的决策集合也可能不同．(4)策略．{ x1(s1)，x2(s2)…，x N(s N)}称为策略．(5)状态转移方程．第k+1阶段的状态s k+l 与第k阶段的状态s k、决策x k之间有函数关系s k+l =T k (s k，x k)，并称其为状态转移方程．(6)权函数．在第k阶段，当状态取定s k、决策取定x k时，该阶段所实现的效益指标(例如距离、时耗、利润、成本等)称为权函数，(7)指标函数．若第k阶段的状态为s k，当采用了最优子策略{ x*k，x*k+1，…，x*N}后，从阶段k到阶段N可获得的效益，称为指标函数，记为f k (s k)．实现f k (s k) 值的x k记为x*k．(8)递归方程．称下列方程为递归方程：f N+1 (s N+1) =0或1，f k(s k)=)}()(),({11)(++∈⨯+kkkkkSDxsfxswoptKK，k=N，N一1， (1)其中，符号opt视问题性质可取面min或max，同时，当符号⊙取加法运算时，取f N+1 (s N+1) =0；当符号⊙取乘法运算时，取f N+1 (s N+1) =1．由于用递归方程和状态转移方程求解动态规划的过程，是由第N阶段向前递归至第1阶段，故这种方法称为逆序解法．综上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤建立动态规划的数学模型：①划分阶段，并正确地定义各阶段状态变量使之具有描述性、无后效性和可知性3个特性，同时确定状态集合；②定义决策变量，确定决策集合：③确定权函数；④建立状态转移方程；⑤确定指标函数；⑥建立递归方程．由状态转移方程和递归方程，用逆序解法对动态规划模型求解，在求得，f1(s1)和x*1后，则按顺序追踪方法寻找最优策略。
例8-2(投资问题)现有资金5百万元，可对3个项目进行投资，投资额均为整数（单位为百万元）．假设2#项目的投资不得超过3百万元，1#和3#项目的投资均不得超过4百万元，3#项目至少要投资1百万元．投资5年后每个项目预计可获得的收益由下表给出。
问如何投资可获得最大的收益．解：本问题是一个静态问题，但可以把它转化成动态问题：将这个投资问题分成3个阶段，在第k阶段要对项目k#进行投资决策．令s k——对k#，…，3#项目允许的投资额；x k——对k#项目的投资额；w(s k，x k)——对k#项目投资x k后的收益：w(s k，x k)= w k（x k）；T k (s k，x k)——s k+l= s k - x k；f k (s k )——当第k 至第3项目允许的投资额为s k 时所能获得的最大收益．为了获得最大收益，必须将5百万元资金全部用于投资．故假想有第4阶段存在时必有s 4= 0．对于本问题，有下列递归方程：{}4411()()0()max ()(),3,2,1k k k k kk k k k x D s f s f s w x f s k ++∈=⎧⎪⎨=+=⎪⎩第一步 K=3第二步K=2第三步K=1s1=5 s2=4 s3=2 x1*=1 x2*=2 x3*=2 f1(5)=21（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。
每个营业区至少设一家，所获利润如表。
问设立的6家销售店数应如何分配，可使总利润最大？解：s k——对k#,…,3#营业区允许设立的销售店数x k——对k#营业区设立的销售店数w k (s k,x k)——对k#营业区设立x k销售店后的利润：w k (s k,,x k)= w k (x k)T k (s k, x k)——s k +1= s k - x kf k(s k)——当第k至第3个营业区允许设立的销售店数为s k时所能获得的最大利润递归方程：f4(s4)=0f k (s k)=max ｛w k (x k)+ f k+1(s k+1)｝, k=3,2,1x k↔D k(s k)第一步：k=3时，有方程f4 (s4)=0f3(s3)= max ｛w3(x3)+ f4(s4) ｝x3↔D3(s3)s3=s2—x2第二步：k=2,有方程f2(s2)= max ｛w2(x2)+ f3(s3) ｝x2↔D2(s2)s3=s2—x2-第三步：k=1,有方程f1(s1)= max ｛w1(x1)+ f2(s2) ｝x1↔D1(s1)s2=s1—x1s1=6 →s2=3 →s3=2↓↓↓x1*=3 x2*=1 x3*=2分别A1、A2、A3营业区设立3家、1家、2家销售店，最大利润为770例8-7(可靠性问题)某种仪表由3种不同的元件串联而成，任一个元件的故障将造成整台仪表的故障．每种元件又都有3种规格，设k#元件j#规格的可靠性为R kj，所需费用为C kj．生产每台仪表的费用限额E为10．试问如何选用各种元件的规格，使得仪表的可靠性最大?我们把这个问题分成3个阶段．在第k阶段要确定k#元件的规格．下面我们用逆序解法求解．s k——仪表上配备k #，…，3#元件时允许使用的费用；s3——仪表上配备3#元件时允许使用的费用；s2——仪表上配备2#, 3#元件时允许使用的费用；s1——仪表上配备1 #，2 #，3#元件时允许使用的费用；x k——k#元件所选用的规格；w k(s k，x k)——k#元件采用规格x k#时的可靠性：w k(s k，x k)=R k x k；T k (s k，x k)——s k+l= s k - C k x k；f k(s k)——在费用限额为s k的条件下，k #， (3)元件串联时相应部分可获得的最大可靠性．递归方程为：f4(s4)=1f k(s k)=)}(),({11)(m ax++∈∙kkkkkSDxsfxswKK，k=3，2，，1。
第一步，k=3，将上表简化：第二步，k=2，f(s2)的计算过程如表所示．将上表简化：第三步，对k=1S1=10 →S2=5 →S3=5 ↓↓↓x*1=3 x*2=1 x*3=2请用动态规划方法求解：max f = x1x2x3s．t．a1x1+ a2x2+a3x3=x1 + 2x2+ x3≤5x1>0，x2>0，x3>0，整数。
设s k：a k x k+---+a3x3的允许值x k：第k阶段x k的取值w k(s k,x k)：w k(s k,x k)= x kT k (s k，x k)：s k+1=s k-a k x kF k(s k):在a k x k+---+a3x3≤s k的条件下，x k---x3能获得的最大值递归方程f4(s4)=1f k(s k)= Max{ x k·f(s k+1) } k=3,2,1 第一步：第二步：第三步：（2分）123123123123T T5421,1,25312,1,1X*112X*211*2s s s x x x s s s x x x f ******∴=→=→=⇒====→=→=⇒===∴或最优解＝（，，）或＝（，，）＝二、加工某产品分别要通过1#、2#、3#三种机器，这些机器的偶然故障，将会影响产品的质量。
但是次品要在生产过程终了时才能检查发觉。
由统计资料知道，这三种机器加工产品的合格率分别为0.7, 0.6, 0.8。
现在管理部门准备再投资5万元来提高产品的合格率。
问如何使用这5万元，使产品合格率最高？解：s k——对k#，…，3#机器允许的投资额；x k——对k#机器的投资额；w(s k，x k)——对k#机器投资x k后的收益：w(s k，x k)= w k（x k）；T k (s k，x k)——s k+l= s k - x k；f k (s k )——当第k #至第3#机器允许的投资额为s k 时所能获得的最大收益．递归方程：{}4411()()1()max ()(),3,2,1k k k k k k k k k x D s f s f s w x f s k ++∈=⎧⎪⎨=∙=⎪⎩第一步：k=3第二步：k=2第三步：k=10.567 0.612 0.612 0.552S1=5 →S2=4 →S3=1↓↓↓x*1=1 x*2=3 x*3=1S1=5 →S2=3 →S3=0↓↓↓x*1=2 x*2=3 x*3=0。
