动态规划 中山纪念中学 宋新波 本模板来源于网络，由第一课件网整理发布，免费分享给大家使用。

Presentation on theme: "动态规划 中山纪念中学 宋新波 本模板来源于网络，由第一课件网整理发布，免费分享给大家使用。"— Presentation transcript:

1 动态规划 中山纪念中学 宋新波 本模板来源于网络，由第一课件网整理发布，免费分享给大家使用。
更多精彩PPT模板，请访问 使用时删除此备注即可。 配色方案修改： 配色方案在【格式】-->【幻灯片设计】-->【配色方案】-->【编辑配色方案】下调整。 LOGO的添加： Logo添加修改在【视图】-->【母版】-->【幻灯片母版】下调整。直接选择logo图片删除或修改。 字体格式的设置： 括标题和文本格式的设置在【视图】-->【母版】-->【幻灯片母版】下调整。

2 动态规划的关键点 最优化原理 子问题最优化结构 无后效性 未来与过去无关 状态 描述最优解的结构 状态转移方程 递归定义最优解的值 程序实现
用记忆化搜索或迭代法求解

3 例1：01背包 有N种物品和一个容量为V的背包。第i种物品只有1个，体积是v[i]，价值是w[i]。选择物品装入背包使这些物品的体积总和不超过背包容量，且价值总和最大，求出这个最大价值。

4 分析 状态：f[i,j]表示用体积为j的背包装前i个物品能获得的最大价值。 考虑第i种物品装或不装进行状态转移:
1.装：f[i-1,j-v[i]]+w[i](必须满足j>=v[i]) 2.不装：f[i-1,j] 两种情况取较大值。 状态转移方程为： i=0(边界条件) f[i,j]= f[i-1,j] j<v[i] max(f[i-1,j],f[i-1,j-v[i]]+w[i]) j>=v[i] 答案为f[n,v]，时间复杂度为O(N*V)。

5 例2：完全背包 有N种物品和一个容量为V的背包。第i种物品有无穷个，体积是v[i]，价值是w[i]。选择物品装入背包使这些物品的体积总和不超过背包容量，且价值总和最大，求出这个最大价值。

6 方法一 状态：f[i,j]表示用体积为j的背包装前i个物品能获得的最大价值。
考虑第i个物品装几个来进行状态转移，假设装x个，x的范围为0<=x<=j div v[i] 状态转移方程： i=0 f[i,j]= max{f[i-1,j-x*v[i]]+x*w[i]} 0<=x<=j div v[i] 答案为f[n,v],时间复杂度为o( )

7 方法二 状态：f[i,j]表示用体积为j的背包装前i个物品能获得的最大价值。 考虑第i个物品装或不装来进行状态转移：
1.装:必须满足j>=v[i]，由于物品有无穷多个，装一次后后面还可以再装，所以状态为f[i,j-v[i]]+w[i]; 2.不装：f[i-1,j] 状态转移方程： i=0 f[i,j]= f[i-1,j] j<v[i] max(f[i-1,j],f[i,j-v[i]]+w[i]) j>=v[i] 答案为f[n,v]，时间复杂度为O(N*V)。

8 例3：多重背包 有N种物品和一个容量为V的背包。第i种物品最多有m[i]件可用，体积是v[i]，价值是w[i]。选择物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

9 方法一 状态：f[i,j]表示用体积为j的背包装前i个物品能获得的最大价值。
跟完全背包方法一相同，考虑第i个物品装几个来进行状态转移，假设装x个，x的范围为0<=x<=min(j div v[i],m[i]) 状态转移方程： i=0 f[i,j]= max{f[i-1,j-x*v[i]]+x*w[i]} 其中0<=x<=min(m[i],j div v[i]) 答案为f[n,v],时间复杂度为O(V* )。

10 方法二 把“m[i]个第i种物品”看作是“m[i]种物品”，每种物品只有一个，体积和价值分别为v[i]和w[i]，这样原问题就转变为 个物品的01背包问题。 时间复杂度也是O(V* )。

11 方法三 应用二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略(取0..m[i]件)均能等价于取若干件代换以后的物品。另外，取超过m[i]件的策略必不能出现。 方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的体积和价值均是原来的体积和价值乘以这个系数。使这些系数分别为 1,2,4,...,2^(k-1),m[i]-2^k+1，其中k满足m[i]-2^k+1<2^k。例如，如果m[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。 如何证明任何x(0<=x<=m[i])都可以用上述系数相加得到？

12 方法三 证明： 当x=0时：只要都不选就可以；
当1<=x<=2^k-1时：把x转为二进制，选择对应位为1的物品。如x=5,5的二进制为101，5=1+4； 当2^k<=x<=m[i]时：由于m[i]-(2^k-1)<2^k，则选择m[i]-(2^k-1)，剩下的为x-m[i]+2^k-1<=2^k-1可以由前面的1,2,...,2^(k-1)组合得到。 物品i可以被分解为 个数量为1的物品，题目就转化为 个物品的01背包。 时间复杂度为O(V* )。

13 方法四 回顾方法一状态转移方程： 0 i=0 f[i,j]= max{f[i-1,j-x*v[i]]+x*w[i]}
0<=x<=min(m[i],j div v[i]) 可以用单调队列优化到O(N*V)。

14 例4：最长上升子序列 给你n个数a1,a2,...,an的序列，要求输出最长上升子序列的长度。

15 方法一 状态：f[i]表示以a[i]结尾的最长上升子序列的长度。
考虑前一个数可能的位置进行状态转移，假设前一个数是a[j]，则必须满足j<i同时a[j]<a[i]，满足条件的j有多个，找出最大的f[j]即可。 状态转移方程为： i=1 f[i]= max{f[j],0}+1 (j<i)and(a[j]<a[i]) 答案为max{f[i]}(1<=i<=n)。时间复杂度为O(n2)。

16 方法二 方法一中计算f[i]时需要从1到i-1逐一枚举j，我们可以记录g[x]表示，以数值x结尾的最长上升子序列的长度，利用树状数组维护g[1..x]的最大值，在计算f[i]时直接利用树状数组计算出g[1..a[i]-1]的最大值。 如果a[i]数值不大可以直接做，否则需要离散化。 时间复杂度为O(nlgn)。

17 方法三 贪心法。 上升子序列的最后一个数越小越好。
记录b[i]表示目前已经计算出来的长度为i的上升子序列的最后一个元素的最小值。数组b是有序的。 依次处理a1,a2..,a[n]，对于a[i],二分求出在b[]数组中插入的位置p，f[i]=p，同时把b[p]改为a[i] 时间复杂度为O(nlgn)。 b[4] 6 i 1 2 3 4 5 6 a[i] f[i] b[3] 5 b[2] 2 4 2 1 3 2 4 b[1] 1 3

18 例5：石子归并一 设有n堆石子排成一排，其编号为1，2，3，…，n（n≤100）。每堆石子有一定的数量，如下表 。现在要将n堆石子归并成一堆。每次只能将相邻的两堆石子堆成一堆，这样经过n-1次归并之后最后成为一堆，如上面7堆沙子，可以有多种方法归并成一堆，其中的2种方法如下图：

19 例5：石子归并一 如上图中，将13和7归并为一堆的代价为20。归并总代价指的是将沙子全部归并为一堆沙子的代价的和，如上面的2种归并方法中，
（a）的总代价为20＋24＋25＋44＋69＋87＝267 （b）的总代价为15＋37＋22＋28＋59＋87＝248 由此可见，不同归并过程得到的总的归并代价是不一样的。 问题：当n堆沙子的数量给出之后，找出一种合理的归并方法，使总的归并代价最小。

20 分析 最后那堆石子是由一开始的n堆石子经过n-1次合并得到，考虑最后一次合并，一定是把两堆石子合并成一堆，那最后一次合并的两堆石子分别是怎么来的，它们分别对应于最初的n堆石子中的哪些石子？ 如图所示，由于每次选择相邻两堆石子合并，所以一定是由第1堆到第i堆合并成其中一堆，另一堆是由第i+1堆到第n堆合并而成。而左上这堆石子又是由1到j合并的石子堆跟j+1到i合并的石子堆这两堆石子合并而成。 1到j合并而成 j+1到i合并而成 i+1到n合并而成 1到i合并而成 1到n合并而成

21 分析 根据上述分析，我们定义f[i,j]表示把第i堆到第j堆石子合并成一堆所需的最小代价。s[i]表示前i堆石子和。
最后一次合并左边一堆由i到k合并而成，右边一堆由k+1到j合并而成，在所有可选择的k中找一个最优的，得到以下状态转移方程： 0 i=j f[i,j]= max{f[i,k]+f[k+1,j]}+s[j]-s[i-1] (i<=k<=j-1) 按照石子堆数划分阶段来实现。 答案为f[1,n],时间复杂度为O(n3)。

22 程序 for i:=1 to n do s[i]:=s[i-1]+a[i]; for L:=2 to n do begin{L表示石子堆数}
for i:=1 to n-L+1 do begin{i表示起始位置} j:=i+L-1;{j表示终点位置} f[i,j]:=maxlongint; for k:=i to j-1 do begin f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]+s[j]-s[i-1]); end; writeln(f[1,n])；

23 例6：石子归并二 设有n堆石子围成一圈，其编号为1，2，3，…，n（n≤100）。每堆石子有一定的数量，如下表 。现在要将n堆石子归并成一堆。每次只能将相邻的两堆石子堆成一堆，这样经过n-1次归并之后最后成为一堆，当n堆沙子的数量给出之后，找出一种合理的归并方法，使总的归并代价最小。

24 方法一 可以把圈看作是n条线，然后再按照“排成一排”的做法来做。 时间复杂度为O(n4),超时。

25 方法二 方法一中把圈看作n条线，这n条线之间有重叠，但方法一把这n条线独立开来做导致有些状态重复计算，所以超时。
f[i,j]表示从第i堆到第j堆合并成一堆所需最少代价，如果j>i则一共有j-i+1堆石子，分别是i,i+1,...,j-1,j，如果j<i，则一共有n-i+1+j堆石子，分别是i,i+1,...,n,1,2,...,j 状态转移方程： 0 i=j f[i,j]= max{f[i,k]+f[k mod n+1,j]}+s1(i,j) 当i<j时s1[i,j]=s[j]-s[i-1],i<=k<=j-1; 当i>j时，s1(i,j)=s[n]-s[i-1]+s[j],k取i,i+1,...n,1,2,...j-1)。 答案为max{f[1,2],f[2,1],f[3,2],f[n,n-1]},时间复杂度为O(n3)。

26 方法二程序 for L:=2 to n do begin{L表示石子堆数}
for i:=1 to n do begin {i为起点，注意i的终值为n} j:=(i+L-2)mod n+1;{j为终点} k:=i;f[i,j]:=maxlongint; while k<>j do begin f[i,j]:=min(f[i,j],f[i,k]+f[k mod n+1,j]+s1(i,j)); k:=k mod n+1; end;

27 方法三 把n个石子堆复制一份变成a1,a2,...,an,a1,a2,...an，状态f[i,j]和转移方程都跟前面类似。这样n条线的最小代价分别对应于f[1,n],f[2,n+1],f[3,n+2]...f[n,2*n-1]，其中最小值就是答案。 时间复杂度为O(n3),程序如下： for i:=n+1 to 2*n do a[i]:=a[i-n]; for L:=2 to n do begin{L表示石子堆数} for i:=1 to 2*n-L do begin{i表示起点} j:=i+L-1;{j表示终点} f[i,j]:=maxlongint; for k:=i to j-1 do f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]+s[j]-s[i-1]); end; end;ans:=f[1,n]; for i:=2 to n do ans:=min(ans,f[i,i+n-1]);

28 例7：加分二叉树(NOIP2003) 设一个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的前序遍历

29 例7：加分二叉树(NOIP2003) 【输入格式】 第1行：一个整数n(n＜30)，为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数(分数＜100) 【输出格式】 第1行：一个整数，为最高加分(结果不会超过4,000,000,000)。 第2行：n个用空格隔开的整数，为该树的前序遍历。 【输入样例】 【输出样例】

30 分析 树的中序遍历=左子树的中序遍历+树根+右子树的中序遍历。
已知中序遍历为1到n，如果树根为i，则1-i-1为这棵树的左子树的中序遍历，而i+1到n为右子树的中序遍历，每一棵子树都对应着序列中一段连续的区域。 定义opt[i,j]表示中序遍历为i到j的树最大加分,如果树根为k，则左子树为i到k-1,右子树为k+1到j，左子树和右子树对应的最大加分为opt[i,k-1]和opt[k+1,j]，满足最优化原理。

31 分析 通过考虑树根k进行状态转移： a[i] i=j(叶子) opt[i,j]= 1 i=j+1(空子树)
max{opt[i,k-1]*opt[k+1,j]+a[k]} i<=k<=j 答案为opt[1,n]，时间复杂度为o(n3)。 对于输出最大加分二叉树的前序，只需增加g[i,j]记录opt[i,j]取最大值所对应的k即树根，再用递归输出前序即可。

32 程序代码——计算opt for i:=1 to n do f[i,i-1]:=1;
for i:=1 to n do opt[i,i]:=a[i]; for L:=2 to n do {L表示序列的长度} for i:=1 to n-L+1 do begin {i表示序列的起点} j:=i+L-1; opt[i,j]:=-maxlongint; for k:=i to j do begin t:=opt[i,k-1]*opt[k+1,j]+a[k]; if t>opt[i,j] then begin opt[i,j]:=t;g[i,j]:=k; end;

33 程序代码——输出前序 procedure print(L,R:integer); begin if L>R then exit;
if L=R then write(L,' ') else begin write(g[L,R],' '); print(L,g[L,R]-1); print(g[L,R]+1,R); end;

34 例8：能量项链(NOIP2006) 【问题描述】 在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。 需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为： (4⊕1)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。

35 例8：能量项链 【输入文件】 输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i<N时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。 【输出文件】 输出文件energy.out只有一行，是一个正整数E（E≤2.1*10^9），为一个最优聚合顺序所释放的总能量。 【输入样例】 4 【输出样例】 710

36 分析 用a[i]表示珠子i的头标记，则把第i个到第j个珠子聚合成一个珠子的头标记为a[i]，尾标记为a[j mod n+1]。
做法跟环形石子归并一样，把n个珠子复制一份，用f[i,j]表示把第i个到第j个珠子聚合成一个珠子的最大能量。 状态转移方程如下： 0 i=j f[i,j]= max{f[i,k]+f[k+1,j]+a[i]*a[k+1]*a[j+1]} i<=k<=j-1 答案=max{f[1,n],f[2,n+1],....,f[n,2*n-1]}。 时间复杂度为O(n^3)。

37 能量项链程序 for i:=n+1 to 2*n do a[i]:=a[i-n]; for L:=2 to n do
for i:=1 to 2*n-L do begin j:=i+L-1; f[i,j]:=0; for k:=i to j-1 do f[i,j]:=max(f[i,j],f[i,k]+f[k+1,j]+a[i]*a[k+1]*a[j+1]); end; ans:=0; for i:=1 to n do ans:=max(ans,f[i,i+n-1]); writeln(ans);

38 例9：凸多边形三角划分 给定一个具有N（3<=N<=50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？ 输入文件：第一行 顶点数N 第二行 N个顶点（从1到N）的权值 输出格式：最小的和的值 输入示例： 4 输出示例：18

39 分析 在递推中已经学习过“凸多边形划分”一题，思路一样，每一种划分都保证多边形的每条边都唯一属于一个三角形，只要把这条边对应的点定下来，这个三角形就是唯一确定的。 状态f[i,j](i<j)表示i到j这j-i+1个顶点形成的凸多边形乘积最小值。注意这个凸多边形共有j-i+1条边，分别是(i,i+1),(i+1,i+2)...(j-1,j)以及(i,j)这条边。 考虑(i,j)这条边所对应的顶点k进行状态转移，i+1<=k<=j-1,此时多边形被分成三个区域，其中区域是i到k形成的凸多边形，区域是△ijk，区域为k到j形成的凸多边形。 0 j=i+1 f[i,j]= min{f[i,k]+f[k,j]+a[i]*a[j]*a[k]} i+1<=k<=j-1 时间复杂度为O(n3)。答案为f[1,n]。 k j i 1 2 3

40 例10：行政划分 【背景】某国领土形状十分奇特，可以将它近似地看作是一个有N个顶点的凸多边形 。现在该国政府想要将它划分为(N-2)个互不重叠的行政区域，并希望每个区域的形状都是三角形，三角形的顶点即为凸多边形的顶点。该国政府又出于资源、人口、宗教等多方面的考虑，希望得到一种划分方案，使得(N-2)块区域的面积的标准差最小 【任务】现在该国政府官员找到了你，希望你能够帮助他们解决这个问题， 【输入格式】第一行是一个整数N (4≤N≤50), 表示凸多边形顶点的个数 接下来的N 行，每行有两个实数X、Y( ≤X、Y≤ )，分别表示按比例缩小后的凸多边形顶点在坐标系内的横纵坐标值。 【输出格式】你只要输出一个实数，即最小标准差值 (保留到百分位)。 【样例输入】 【样例输出】 0 0 1 0 1 1 0 1

41 分析 标准差= ，只要保证 标准差一定最小。 所以本题就转化为求一种划分方案使得n-2个三角形的面积平方和最小。方法同例9，同学们自己完成。

42 例11：等腰三角形 给定一个正N边形，可以通过连线将这个多边形分割成N-2个三角形，问这N-2个三角形中恰有k个等腰三角形的分割方法有多少？这个值可能很大，输出对9397取模的结果。 输入格式:第一行一个数n和k。(3<=n<=50，0<=k<=n-2). 输出格式:一个整数，表示正n边形切割成n-2个三角形，其中恰有k个等腰三角形的分割方法，结果模9397。 样例输入: 样例输出: 注释:于第一种情况下，我们之间可以有一个顶点0和2或1和3之间的对角顶点。在这两种情况下，有2个等腰的三角形。对于第二个案件中，只有一个等边三角形的分割不含对角线，只有一等腰三角形（多边形本身）。 对于第三种情况，一个正五边形有5个三角剖分。每个顶点都与它们不相邻的两点连接。

43 方法一 状态f[i,j,k]表示以i到j这j-i+1个点为顶点形成的凸多边形划分成j-i-1个互不相交的三角形，其中有k个等腰三角形的方案数。 考虑(i,j)这条边对应的顶点x，另还要考虑i到x的凸多边形中有多少个等腰三角形进行状态转移。 如何判断(i,j,x)是否是等腰三角形？ 由于是正N边形，所以三条边的长度可以看作是x-i,j-x,j-i。定义judge(i,j,k)判断i,j,k三点形成的三角形是否是等腰三角形。如果是则返回1否则返回0。 状态转移方程如下： (j=i+1)and(k=0) f[i,j,k]= j>i+1 答案为f[1,n,k]。时间复杂度为O(N3*K2)。

44 方法二 可以在方法一的基础上优化状态，方法一中用两个参数i,j来表示一个凸多边形，由于是正N边形，可以用一个参数记录点数即可。
g[i,j]表示把以i个连续点为顶点的凸多边形划分成i-2个三角形其中有j个等腰三角形的方案数。 状态转移方程为： (i=2)and(j=0) g[i,j]= i>=3 答案为g[n,k]。时间复杂度为O(N2*K2)。

45 例12：最优配对问题 平面上有n个点P1,P2,...,Pn,你的任务是把它们配成n/2对(n是偶数)，使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。n<=20,|xi|,|yi|<=10000。

46 方法一 n<=20,容易想到用搜索来解决，每次从未配对的点中选两个点配对再继续搜。定义全局数组f:array[0..20]of boolean；f[i]=false表示i未配对，f[i]=true表示i已经配对，dis(i,j)表示Pi到Pj的距离，答案ans一开始赋为 。

47 方法一程序 procedure dfs(remain:integer;d:real);{remain表示剩下的点数，d表示当前的距离}
var i,j:integer; Begin if d>=min then exit;{最优化剪枝} if remain=0 then ans:=d {到达递归出口} else for i:=1 to n-1 do if not f[i] then {枚举i和j配对} for j:=i+1 to n do if not f[j] then begin f[i]:=true;f[j]:=true; dfs(remain-2,d+dis(i,j)); f[i]:=false;f[j]:=false; end; 时间复杂度为 ，超时。

48 方法二 方法一有很多方案被重复计算了，如n=4，(1,3)(2,4)和(2,4)(1,3)是同一种方案，但被计算了两次。
由于每个点都要配对，我们可以按照P1,P2,...Pn的顺序来依次寻找跟它们配对的点

49 方法二程序 procedure dfs(x:integer;d:real);{x表示下一个要配对的点} var y:integer;
Begin if d>=min then exit;{最优化剪枝} if x=n+1 then ans:=min(ans,d) else if f[x] then dfs(x+1,d) else for y:=x+1 to n do if not f[y] then begin f[y]:=true;dfs(x+1,d+dis(x,y));f[y]:=false; end; 时间复杂度为n!/(2^(n/2)*(n/2)!) ,比方法一快了很多，但还是超时。

50 方法三 方法二中依然存在状态重复计算。如n=8,目前已经搜到的配对有2个，分别是(1,3)(2,4),还有5678未配对，另一种搜到了(1,4)(2,3),剩余未配对的也是5678,那么寻找5678配对方案就被重复搜索了。 要解决这个问题，需要用记忆化搜索，此时本质上已经是动态规划了，要用记忆化搜索，必须首先确定好状态的参数，这里的参数实际就是一些未配对的点的集合，集合不方便存储，采用二进制压缩存储，每个点对应一个二进制位，未配对的记为1，已经配对的记为0。如n=8,未配对的点为1,3,5,7，则对应的二进制为 ，对应的十进制为85，则把(1,3,5,7)配对的最小值存储在f[85]中。 f[i]表示把配对情况二进制值为i中的未配对点进行配对获得最小距离。通过考虑下一个配对点进行状态转移： f[i]=min(f[i xor(1 shl (x-1))xor(1 shl(y-1))]+dis(x,y)) (i and(1 shl(x-1))<>0)and(i and(1 shl(y-1))<>0)

51 方法三程序 for i:=1 to 1 shl n-1 do begin f[i]:=100000000;
for x:=1 to n-1 do begin if i and (1 shl(x-1))<>0 then begin for y:=x+1 to n do begin if i and(1 shl(y-1)) then f[i]:=min(f[i],f[i xor(1 shl(x-1))xor(1 shl (y-1))]+dis(x,y)); end; 时间复杂度为O(2n*n2)，仍然超时。

52 方法四 方法三中有重复计算，x不用枚举每一种情况，直接在未配对点中选择最小的点作为x。
for i:=1 to 1 shl n-1 do begin f[i]:= ; for x:=1 to n-1 do if i and (1 shl(x-1))<>0 then break； for y:=x+1 to n do begin if i and(1 shl(y-1))<>0 then f[i]:=min(f[i],f[i xor(1 shl(x-1))xor(1 shl (y-1))]+dis(x,y)); end; 时间复杂度为O(n*2n)。 证明查找第一个未配对的点x平均判断次数不超过2。

53 证明 用i表示第一次出现1的位置，1<=i<=n,第一次出现1的位置为i的数有2n-i。设T表示总判断次数。则有：
平均值=T/(2n)<2

54 例13：Islands and Bridges(poj2288)
给你一幅地图，地图上有岛屿和桥梁，桥梁连接着岛屿,众所周知，汉密尔顿路是指通过桥梁经过每个岛屿一次而且只有一次的路径。在这个地图中，每个岛屿有个正整数的旅游价值，我们要找一条旅游价值最大的汉密尔顿路。 假设有n个岛屿，汉密尔顿路C1C2...Cn的价值分三个部分，假设Ci岛屿的价值为Vi。 第一部分：所有岛屿价值之和； 第二部分：路径中相邻两个岛屿的价值之积，即对于路径中的CiCi+1，我们把ViVi+1加入总价值中； 第三部分：路径中相邻三个岛屿CiCi+1Ci+2，如果Ci和Ci+2之间有桥梁连接，则把Vi*Vi+1*Vi+2加入总价值。 要求计算汉密尔顿路的最大价值，以及方案数。

55 例13：Islands and Bridges 输入：第一行输入q(q<=20)表示测试数据个数。对于每个测试数据，第一行输入两个整数n(n<=13)和m，表示岛屿和桥梁的数量，下一行包含n个正整数，第i个数为Vi(0<Vi<=100),接下来m行，每行包含两个整数x y，表示岛屿x和岛屿y之间有桥梁连接，岛屿编号为1到n 输出：对于每个测试数据，输出两个用空格隔开的整数，第一个数表示汉密尔顿路的最大价值，第二个数表示达到该价值的路径方案数。如果不存在汉密尔顿路输出“0 0”。 注意：一条路径可以以相反的方向去行走，我们认为这两条路径是同一条路径。 样例输入： 样例输出： 2 2 2 1 2 2 3 3 1 4 6 1 3 1 4 2 4 3 4

56 方法一 搜索 时间复杂度O(N!),13!= ,超时

57 方法二 状态压缩DP 用F[i,j,s]表示以i、j两个岛屿开头，岛屿经过情况为s，走完s中未经过的岛屿所能获得的最大价值。
通过考虑紧跟在i，j后面的岛屿k得到以下状态转移方程 F[i,j,s]=max(Vk*Vj+Vi*Vj*Vk(if a[i,k]=1)+F[j,k,s']) 其中k满足(a[j,k]=1)and(s and (1 shl(k-1))<>0),s1’=s xor(1 shl(k-1)) 时间复杂度为O(N3*2N),最坏

58 例14：最大利润 政府邀请了你在火车站开饭店，但不允许同时在两个相连接的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有50个和它相连接的火车站。 告诉你每个火车站的利润，问你可以获得的最大利润为多少。 例如下图是火车站网络： 最佳投资方案是在1，2，5，6这4个火车站开饭店可以获得利润为90

59 例14：最大利润 输入：第一行输入整数N(<=100000)，表示有N个火车站，分别用1，2。。。，N来编号。接下来N行，每行一个整数表示每个站点的利润，接下来N-1行描述火车站网络，每行两个整数，表示相连接的两个站点。 输出：输出一个整数表示可以获得的最大利润。 样例输入： 样例输出： 10 20 25 40 30 4 5 1 3 3 4 2 3 6 4

60 分析 任意两个火车站有且只有一条路径，是一棵树。
我们用f[x]表示在以x为根的树中开饭店，x一定要开，所能获得的最大利润，g[x] 表示在以x为根的树中开饭店，x一定不开，所能获得的最大利润，如果x开，则它的儿子们y1,…yk一定不能开，如果x不开，它的儿子们可开可不开，于是得到以下状态转移方程： f[x]= a[x] (yi是x的儿子) g[x]= (yi是x的儿子) 实现时用dfs去实现，每个点只需求一次，所以时间复杂度为O(N)。

61 例15：选课 大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。 每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。

62 例15：选课 下面举例说明 例子中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。
学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

63 例15：选课 输入： 输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学生可以选的课程总数（1≤N≤M)。 以下M行每行代表一门课，课号依次为1，2……M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。 输出： 输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。

64 分析 根据“每门课的直接选修课最多只有一门”这个条件可以知道该题目的模型是由若干棵树构成的森林。
如下左边为输入数据，右图为输入数据对应的森林。 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 1 5 7 3 4 6

65 方法一 首先添加一个0号结点，让森林中的所有树根都成为0号结点的儿子，从而把森林转化为一棵树。如下图所示： 2 1 5 7 3 4 6 2
2 1 5 7 3 4 6

66 方法一 定义f[i,j]表示在以i为根的子树中选修j门课程所能获得的最大学分。 f[i,0]=0;
时间复杂度极高，超时。

67 方法二 方法一之所以超时，是由于“树”，树的儿子数量可能比较多，这样转移花费大量时间，我们可以把树等价转变为二叉树。
左儿子右兄弟法：结点的第一个儿子作为左儿子，右兄弟作为右儿子。 2 1 5 7 3 4 6

68 方法二 f[i,j]表示在以i为根的子树中选修j门课程能获得的最多学分。 根据i选不选分两种情况：
1.不选：那i及i的左子树都不能选，全部在i的右子树中选，f[rightson,j]; 2.选：i选，i的左子树可以选也可以不选，假设左子树选k个，则另外j-1-k在右子树中选，对应的状态为f[leftson,k]+f[rightson,j-1-k]; 用自顶向下记忆化搜索实现，时间复杂度为O(mn2)。

69 方法三 不需要转变成二叉树。 f[i,j]表示在以i为根的子树中选修j门课程能获得的最多学分。
方法一的方法采用自顶向下，所以复杂度很高，我们可以考虑用自下向上。 fa[i]存储i的父结点，我们把fa[i]的儿子们看作是个个物品，当我们计算完f[i,j]后把(j,f[i,j])看作是背包中的一个物品，其中j是体积，f[i,j]是价值，用这个物品去更新f[fa[i],k](k>=j)更新的方法跟背包问题一样。程序段如下： for k:=n downto j do if f[fa[i],k-j]+f[i,j]>f[fa[i],k] then f[fa[i],k]:=f[fa[i],k-j]+f[i,j]; 用BFS得到一个序列，从后往前执行更新。 时间复杂度为O(m*n2)。

70 谢谢！