《动态规划基础讲解及经典案例分析解答课件.ppt》由会员分享，可在线阅读，更多相关《动态规划基础讲解及经典案例分析解答课件.ppt（60页珍藏版）》请在三一办公上搜索。
1、第九课,动态规划(I),综合实践考核,10/2/2022,1,第九课动态规划(I)综合实践考核10/2/20221,数字三角形,1、问题描述,上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。,数字三角形 1、问题描述 上图给出了一个数字三角形。从三角形,问题描述,输入数据输入的第一行是一个整数N(1 N=100)，给出三角形的行数。下面的N 行给出数字三角形。数字三角形上的数的范围都在0
2、和100 之间。输出要求输出最大的和。,问题描述输入数据,问题描述,输入样例573 88 1 02 7 4 44 5 2 6 5输出样例30,问题描述输入样例,2、解题思路,这道题目可以用递归的方法解决。基本思路是：以D(r,j)表示第r 行第 j 个数字(r，j 都从1 开始算)，以MaxSum(r,j)代表从第 r 行的第 j 个数字到底边的最佳路径的数字之和，则本题是要求 MaxSum(1,1)。从某个D(r,j)出发，显然下一步只能走D(r+1,j)或者D(r+1,j+1)。如果走D(r+1,j)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j)+D(r,j)；如果走D(
3、r+1,j+1)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j+1)+D(r,j)。所以，选择往哪里走，就看MaxSum(r+1,j)和MaxSum(r+1,j+1)哪个更大了。,2、解题思路 这道题目可以用递归的方法解决。基本思路是：,3、参考程序 I,#include#define MAX_NUM 100int DMAX_NUM+10MAX_NUM+10;int N;int MaxSum(int r,int j)if(r=N)return Drj;int nSum1=MaxSum(r+1,j);int nSum2=MaxSum(r+1,j+1);if(nSum1 nSum2
4、)return nSum1+Drj;return nSum2+Drj;,3、参考程序 I#include,3、参考程序 I,int main(void)int m;scanf(%d,提交结果：Time Limit Exceed,3、参考程序 Iint main(void)提交结果：Tim,程序I分析,上面的程序，效率非常低，在N 值并不大，比如N=100 的时候，就慢得几乎永远算不出结果了。为什么会这样呢？是因为过多的重复计算。我们不妨将对MaxSum 函数的一次调用称为一次计算。那么，每次计算MaxSum(r,j)的时候，都要计算一次MaxSum(r+1,j+1)，而每次计算MaxSum(r
5、,j+1)的时候，也要计算一次MaxSum(r+1,j+1)。重复计算因此产生。在题目中给出的例子里，如果我们将MaxSum(r,j)被计算的次数都写在位置（r,j），那么就能得到右面的三角形：,11 11 2 11 3 3 11 4 6 4 1,73 88 1 02 7 4 44 5 2 6 5,程序I分析 上面的程序，效率非常低，在N 值并不大，比如N=,程序分析,从上图可以看出，最后一行的计算次数总和是16，倒数第二行的计算次数总和是8。不难总结出规律，对于N 行的三角形，总的计算次数是20+21+22+2(N-1)=2N-1。当N=100 时，总的计算次数是一个让人无法接受的大数字。既
6、然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出MaxSum(r,j)的值时，就将该值存放起来，下次再需要计算MaxSum(r,j)时，直接取用存好的值即可，不必再次调用MaxSum 进行函数递归计算了。这样，每个MaxSum(r,j)都只需要计算1 次即可，那么总的计算次数（即调用MaxSum 函数的次数）就是三角形中的数字总数，即1+2+3+N=N(N+1)/2。如何存放计算出来的MaxSum（r,j）值呢？显然，用一个二维数组aMaxSumNN就能解决。aMaxSumrj就存放MaxSum(r,j)的计算结果。下次再需要MaxSum
7、(r,j)的值时，不必再调用MaxSum 函数，只需直接取aMaxSumrj的值即可。,程序分析 从上图可以看出，最后一行的计算次数总和是16，倒,4、参考程序 II,#include#include#define MAX_NUM 100int DMAX_NUM+10MAX_NUM+10;int N;int aMaxSumMAX_NUM+10MAX_NUM+10;int MaxSum(int r,int j)if(r=N)return Drj;if(aMaxSumr+1j=-1)/如果MaxSum(r+1,j)没有计算过 aMaxSumr+1j=MaxSum(r+1,j);if(aMaxSum
8、r+1j+1=-1)aMaxSumr+1j+1=MaxSum(r+1,j+1);if(aMaxSumr+1j aMaxSumr+1j+1)return aMaxSumr+1j+Drj;return aMaxSumr+1j+1+Drj;,4、参考程序 II#include,4、参考程序 II,int main(void)int m;scanf(%d,4、参考程序 IIint main(void),程序II分析,这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是
9、最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：,因此，不需要写递归函数，从aMaxSumN-1这一行元素开始向上逐行递推，就能求得aMaxSum11的值了。,程序II分析 这种将一个问题分解为子问题递归求解，并,5、参考程序 III,int DMAX_NUM+10MAX_NUM+10;int N;int aMaxSumMAX_NUM+10MAX_NUM+10;int main(void)int i,j;scanf(%d,思考题：上面的几个程序只算出了最佳路径的数字之
10、和。如果要求输出最佳路径上的每个数字，该怎么办？,5、参考程序 IIIint DMAX_NUM+10,动态规划解题的一般思路,许多求最优解的问题可以用动态规划来解决。首先要把原问题分解为若干个子问题。注意单纯的递归往往会导致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就要被保存，所以每个子问题只需求解一次。子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的n 变成了n-1，或从原来的nm 变成了n(m-1)等等。找到子问题，就意味着找到了将整个问题逐渐分解的办法。分解下去，直到最底层规模最小的的子问题可以一目了然地看出解。每一层子问题的解决，会导致上一层子问题的解决，逐
11、层向上，就会导致最终整个问题的解决。如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程的时候就不需要写递归函数。,动态规划解题的一般思路 许多求最优解的问题可以用动态规划来,动态规划解题的一般思路,用动态规划解题时，将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题，所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。比如数字三角形，子问题就是“从位于(r，j)数字开始，到底边路径的最大和”。这个子问题和两个变量r 和j 相关，那么一个“状态”，就是r,j 的一组取值，即每个数字的位置就是一个“状态”。该“状态”所对应的“值
12、”，就是从该位置的数字开始，到底边的最佳路径上的数字之和。定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移即如何从一个或多个“值”已知的“状态”，求出另一个“状态”的“值”。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。,动态规划解题的一般思路 用动态规划解题时，将和子问题相关的,动态规划解题的一般思路,用动态规划解题，如何寻找“子问题”，定义“状态”，“状态转移方程”是什么样的，并没有一定之规，需要具体问题具体分析，题目做多了就会有感觉。甚至，对于同一个问题，分解成子问题的办法可能不止一种，因而“状态”也可以有不同的定义方法。不同的“状
13、态”定义方法可能会导致时间、空间效率上的区别。,动态规划解题的一般思路 用动态规划解题，如何寻找“子问题”，,最长上升子序列,1、问题描述,一个数的序列bi，当b1 b2.bS 的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,.,aN)，我们可以得到一些上升的子序列(ai1,ai2,.,aiK)，这里1=i1 i2.iK=N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,8).你的任务，就是对于给定的序列，求出最长上升子序列的长度。,最长上升子序列 1、问题描述 一个数的
14、序列bi，当b,问题描述,输入数据输入的第一行是序列的长度N(1=N=1000)。第二行给出序列中的N 个整数，这些整数的取值范围都在0 到10000。输出要求最长上升子序列的长度。输入样例71 7 3 5 9 4 8输出样例4,问题描述输入数据,2、解题思路,如何把这个问题分解成子问题呢？经过分析，发现“求以ak（k=1,2,3N）为终点的最长上升子序列的长度”是个好的子问题这里把一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N 个子问题都解决了，那么这N 个子问题的解中，最大的那个就是整个问题的解。由上所述的子问题只和一个变量相
15、关，就是数字的位置。因此序列中数的位置k 就是“状态”，而状态 k 对应的“值”，就是以ak 做为“终点”的最长上升子序列的长度。这个问题的状态一共有N 个。状态定义出来后，转移方程就不难想了。,2、解题思路 如何把这个问题分解成子问题呢？经过分析，发现,2、解题思路,假定MaxLen(k)表示以ak 做为“终点”的最长上升子序列的长度，那么：MaxLen(1)=1MaxLen(k)=Max MaxLen(i)：1i k 且 ai ak 且 k1+1这个状态转移方程的意思就是，MaxLen(k)的值，就是在ak 左边，“终点”数值小于ak，且长度最大的那个上升子序列的长度再加1。因为ak 左边
16、任何“终点”小于ak 的子序列，加上ak 后就能形成一个更长的上升子序列。实际实现的时候，可以不必编写递归函数，因为从 MaxLen(1)就能推算出MaxLen(2)，有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3),2、解题思路 假定MaxLen(k)表示以ak 做为“终点,3、参考程序,int bMAX_N+10;int aMaxLenMAX_N+10;int main(void)int i,j,N;scanf(%d,3、参考程序int bMAX_N+10;,3、参考程序,for(i=2;i bj)if(nTmp aMaxLenj)nTmp=aMaxLenj;aMax
17、Leni=nTmp+1;int nMax=-1;for(i=1;i=N;i+)if(nMax aMaxLeni)nMax=aMaxLeni;printf(%dn,nMax);return 0;,思考题：改进此程序，使之能够输出最长上升子序列,3、参考程序 for(i=2;i=N;i+,Help Jimmy,1、问题描述,Help Jimmy 是在下图所示的场景上完成的游戏：,Help Jimmy 1、问题描述 Help Jimmy,问题描述,场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。Jimmy 老鼠在时刻0 从高于所有平台的某处开始下落，它的下落速度始终为1
18、 米/秒。当Jimmy 落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1 米/秒。当Jimmy 跑到平台的边缘时，开始继续下落。Jimmy 每次下落的高度不能超过MAX 米，不然就会摔死，游戏也会结束。设计一个程序，计算Jimmy 到地面时可能的最早时间。,问题描述 场景中包括多个长度和高度各不相同的平台。地面,问题描述,输入数据 第一行是测试数据的组数t（0=t=20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N 是平台的数目（不包括地面），X 和Y 是Jimmy 开始下落的位置的横竖坐标，MAX 是一次下落的最大高度。接下来的N 行每行描述一个平台，
19、包括三个整数，X1i，X2i和Hi。Hi表示平台的高度，X1i和X2i表示平台左右端点的横坐标。1=N=1000，-20000=X,X1i,X2i=20000，0 Hi Y=20000（i=1.N）。所有坐标的单位都是米。Jimmy 的大小和平台的厚度均忽略不计。如果Jimmy 恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy 一定能安全到达地面。,问题描述输入数据,问题描述,输出要求对输入的每组测试数据，输出一个整数，Jimmy 到地面时可能的最早时间。输入样例13 8 17 200 10 80 10 134 14 3输出样例23,问题描述输出要求,2
20、、解题思路,此题目的“子问题”是什么呢？Jimmy 跳到一块板上后，可以有两种选择，向左走或向右走。走到左端和走到右端所需的时间，容易算出。如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面的最短时间，那么向左走还是向右走，就很容选择了。因此，整个问题就被分解成两个子问题，即Jimmy 所在位置下方第一块板左端为起点到地面的最短时间，和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。将板子从上到下从1 开始进行无重复的编号(高度相同的板子，哪块编号在前无所谓)，那么，和上面两个子问题相关的变量就只有板子的编号。,2、解题思路 此题目的“子问题”是什么呢
21、？,2、解题思路,所以，本题目的“状态”就是板子编号，而一个“状态”对应的“值”有两部分，是两个子问题的解，即从该板子左端出发到达地面的最短时间，和从该板子右端出发到达地面的最短时间。不妨认为Jimmy 开始的位置是一个编号为0，长度为0 的板子，假设LeftMinTime(k)表示从k 号板子左端到地面的最短时间，RightMinTime(k)表示从k 号板子右端到地面的最短时间，那么，求板子k 左端点到地面的最短时间的方法如下：if(板子k 左端正下方没有别的板子)if(板子k 的高度 h(k)大于Max)LeftMinTime(k)=;else LeftMinTime(k)=h(k);e
22、lse if(板子k 左端正下方的板子编号是m)LeftMinTime(k)=h(k)-h(m)+Min(LeftMinTime(m)+Lx(k)-Lx(m),RightMinTime(m)+Rx(m)-Lx(k);,2、解题思路 所以，本题目的“状态”就是板子编号，而一个“,2、解题思路,上面，h(i)就代表i 号板子的高度，Lx(i)就代表i 号板子左端点的横坐标，Rx(i)就代表i号板子右端点的横坐标。那么 h(k)-h(m)当然就是从k 号板子跳到m 号板子所需要的时间，Lx(k)-Lx(m)就是从m 号板子的落脚点走到m 号板子左端点的时间，Rx(m)-Lx(k)就是从m号板子的落脚
23、点走到右端点所需的时间。求RightMinTime(k)的过程类似。不妨认为Jimmy 开始的位置是一个编号为0，长度为0 的板子，那么整个问题就是要求LeftMinTime(0)。输入数据中，板子并没有按高度排序，所以程序中一定要首先将板子排序。,2、解题思路 上面，h(i)就代表i 号板子的高度，Lx(,3、参考程序,#include#include#include#define MAX_N 1000#define INFINITE 1000000int t,n,x,y,max;struct Platform int Lx,Rx,h;Platform aPlatformMAX_N+10;i
24、nt aLeftMinTimeMAX_N+10;int aRightMinTimeMAX_N+10;int MyCompare(const void*e1,const void*e2)Platform*p1,*p2;p1=(Platform*)e1;p2=(Platform*)e2;return p2-h-p1-h;/从大到小排列,3、参考程序#include,3、参考程序,int MinTime(int L,bool bLeft)int y=aPlatformL.h;int i,x;if(bLeft)x=aPlatformL.Lx;else x=aPlatformL.Rx;for(i=L+1
25、;i=x)break;if(i max)/太高 return INFINITE;,3、参考程序int MinTime(int L,bool,3、参考程序,else/没找到 if(y max)/离地面太高 return INFINITE;else return y;/特殊情况处理完毕 int nLeftTime=y-aPlatformi.h+x-aPlatformi.Lx;int nRightTime=y-aPlatformi.h+aPlatformi.Rx-x;if(aLeftMinTimei=-1)/还没有存储值 aLeftMinTimei=MinTime(i,true);if(aRight
26、MinTimei=-1)aRightMinTimei=MinTime(i,false);nLeftTime+=aLeftMinTimei;nRightTime+=aRightMinTimei;if(nLeftTime nRightTime)return nLeftTime;return nRightTime;,3、参考程序 else/没找到,3、参考程序,int main(void)scanf(%d,思考题：重新编写此程序，要求不使用递归函数,3、参考程序int main(void)思考题：重新编写此程,第十课,动态规划(II),综合实践考核,10/2/2022,34,第十课动态规划(II)综
27、合实践考核10/2/202234,最长公共子序列,1、问题描述,我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列，使得对j=1,2,.,k,有xij=zj。比如Z=是X=的子序列。现在给出两个序列X 和Y，你的任务是找到X 和Y 的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z 既是X 的子序列也是Y 的子序列。输入数据输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200 的字符串，表示两个序列。两个字符串之间由若干个空格隔开。,最长公共子序列 1、问题描述 我们称序列Z=,问题描述,输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。输入样例
28、 abcfbc abfcab programming contest abcd mnp 输出样例 4 2 0,问题描述 输出要求,2、解题思路,用字符数组s1、s2存放两个字符串，用s1i表示s1中的第i 个字符，s2j表示s2中的第j个字符（字符编号从1 开始），用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前j个字符构成的子串，MaxLen(i,j)表示s1i 和s2j 的最长公共子序列的长度，那么递推关系如下：if(i=0|j=0)MaxLen(i,j)=0/两个空串的最长公共子序列长度是0else if(s1i=s2j)MaxLen(i,j)=MaxLen(i-1,j-1)
29、+1;else MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j);,2、解题思路 用字符数组s1、s2存放两个字符串，用s1i,2、解题思路,显然本题目的“状态”就是s1 中的位置i 和s2 中的位置j。“值”就是MaxLen(i,j)。状态的数目是s1 长度和s2 长度的乘积。可以用一个二维数组来存储各个状态下的“值”。本问题的两个子问题，和原问题形式完全一致的，只不过规模小了一点。,2、解题思路 显然本题目的“状态”就是s1 中的位置i 和,3、参考程序,#include#include#define MAX_LEN 1000char sz1MAX_L
30、EN;char sz2MAX_LEN;int aMaxLenMAX_LENMAX_LEN;int main(void)while(scanf(%s%s,sz1+1,sz2+1)0)int nLength1=strlen(sz1+1);int nLength2=strlen(sz2+1);int i,j;for(i=0;i=nLength1;i+)aMaxLeni0=0;for(j=0;j=nLength2;j+)aMaxLen0j=0;,3、参考程序#include,3、参考程序,for(i=1;i nLen2)aMaxLenij=nLen1;else aMaxLenij=nLen2;prin
31、tf(%dn,aMaxLennLength1nLength2);return 0;,3、参考程序 for(i=1;i=,陪审团的人选,1、问题描述,在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪审团的候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0 到20。为了公平起见，法官选出陪审团的原则是：选出的m 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选
32、出的方案称为陪审团方案。,陪审团的人选 1、问题描述 在遥远的国家佛罗布尼亚，,问题描述,输入数据输入包含多组数据。每组数据的第一行是两个整数n 和m，n 是候选人数目，m 是陪审团人数。注意，1=n=200,1=m=20 而且 m=n。接下来的n 行，每行表示一个候选人的信息，它包含2 个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0输出要求对每组数据，先输出一行，表示答案所属的组号,如 Jury#1,Jury#2,等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编
33、号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。,问题描述输入数据,问题描述,输入样例4 21 22 34 16 20 0输出样例Jury#1Best jury has value 6 for prosecution and value 4 for defence:2 3,问题描述输入样例,2、解题思路,为叙述方便，将任一选择方案中，辩方总分和控方总分之差简称为“辩控差”，辩方总分和控方总分之和称为“辩控和”。第i 个候选人的辩方总分和控方总分之差记为V(i)，辩方总分和控方总分之和记为S(i)。现用f(j,k)表示，取j 个候选人，使其辩控差为k 的所有方案中，辩控和最大的那个
34、方案（该方案称为“方案f(j,k)”）的辩控和。并且，我们还规定，如果没法选j 个人，使其辩控差为k，那么f(j,k)的值就为-1，也称方案f(j,k)不可行。本题是要求选出m 个人，那么，如果对k 的所有可能的取值，求出了所有的f(m,k)(-20m k 20m)，那么陪审团方案自然就很容易找到了。,2、解题思路 为叙述方便，将任一选择方案中，辩方总分和控方总,2、解题思路,问题的关键是建立递推关系。显然，方案f(j,k)是由某个可行的方案f(j-1,x)(-20m x 20m)演化而来的。可行方案f(j-1,x)能演化成方案f(j,k)的必要条件是：存在某个候选人i，i 在方案f(j-1,
35、x)中没有被选上，且x+V(i)=k。在所有满足该必要条件的f(j-1,x)中，选出 f(j-1,x)+S(i)的值最大的那个，那么方案f(j-1,x)再加上候选人i，就演变成了方案 f(j,k)。由上面知一个方案都选了哪些人需要全部记录下来。不妨将方案f(j,k)中最后选的那个候选人的编号，记在二维数组的元素pathjk中。那么方案f(j,k)的倒数第二个人选的编号，就是pathj-1k-Vpathjk。假定最后算出了方案的辩控差是k，那么从pathmk出发，就能顺藤摸瓜一步步求出所有被选中的候选人。,2、解题思路 问题的关键是建立递推关系。显然，方案f(j,2、解题思路,初始条件，只能确定
36、f(0,0)=0。由此出发，一步步自底向上递推，就能求出所有的可行方案f(m,k)(-20m k 20m)。实际解题的时候，会用一个二维数组f 来存放f(j,k)的值。而且，由于题目中辩控差的值k 可以为负数，而程序中数租下标不能为负数，所以，在程序中不妨将辩控差的值都加上20m，以免下标为负数导致出错，即题目描述中，如果辩控差为0，则在程序中辩控差为20m。,2、解题思路 初始条件，只能确定f(0,0)=0。由此,3、参考程序,#include#include#include int f301000;int Path301000;int P300;/控方打分int D300;/辩方打分int
37、 Answer30;/存放最终方案的人选int CompareInt(const void*e1,const void*e2)return*(int*)e1)-*(int*)e2);,3、参考程序#include,3、参考程序,int main(void)int i,j,k;int t1,t2;int n,m;int nMinP_D;/辩控双方总分一样时的辩控差 int nCaseNo;/测试数据编号 nCaseNo=0;scanf(%d%d,/选0 个人辩控差为0 的方案，其辩控和就是0,3、参考程序int main(void),3、参考程序,for(j=0;j=0)/方案 f(j,k)可行
38、 for(i=1;ifj+1k+Pi-Di)/即时判别记住更合适的f(j,k)t1=j;t2=k;while(t10,3、参考程序 for(j=0;jm;j+),3、参考程序,i=nMinP_D;j=0;while(fmi+jfmi-j)/绝对值相同时找辩控和最大的 k=i+j;else k=i-j;printf(Jury#%dn,nCaseNo);printf(Best jury has value%d for prosecution and value%d for defence:n,(k-nMinP_D+fmk)/2,(fmk-k+nMinP_D)/2);for(i=1;i=m;i+)A
39、nsweri=Pathm-i+1k;k-=PAnsweri-DAnsweri;/减去辩控差 qsort(Answer+1,m,sizeof(int),CompareInt);for(i=1;i=m;i+)printf(%d,Answeri);printf(n);printf(n);scanf(%d%d,3、参考程序 i=nMinP_D;,购物问题,1、问题描述,由于换季，ACM商场推出优惠活动，以超低价格出售若干种商品。但是，商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究过，我们发现，商场出售的超低
40、价商品中，不存在以下这种情况：N(3=n)种商品C1,C2,Cn，其中Ci和Ci+1是不能同时购买的(i=1,2,n-1)，而且C1和Cn也不能同时购买。请编程计算可以节省的最大金额数。,购物问题 1、问题描述 由于换季，ACM商场推出优惠活动，以,问题描述,输入数据第1行两个整数K,M(1=k=1000)，其中K表示超低价商品数，K种商品的编号依次为1,2,K；M表示不能同时购买的商品对数。接下来K行，第i行有一个整数Xi表示购买编号为i的商品可以节省的金额(1=Xi=100)。再接下来M行，每行两个数A和B，表示A和B不能同时购买，1=A=K，1=B=K，AB。输出要求仅一个整数，表示能节
41、省的最大金额数。,问题描述输入数据,问题描述,输入样例3 11111 2输出样例2,问题描述输入样例,2、解题思路,本题关键是构造一个结点带权的图，结点表示超低价商品，结点的权值表示购买该商品能节省的金额，边表示边所连的两个点的商品不能同时购买。这样就相当于在图中找出一个点集，使该点集中任两点没有连边而且权值之和最大。依题意，该图是无环图，所以该图由若干棵树组成。只要把每棵树的相应最大节省金额求出来再求和即得结果。,2、解题思路 本题关键是构造一个结点带权的图，结点表,2、解题思路,对于单棵树，可以用动态规划的方法求出结果，方法如下：(1)对该棵树广度或深度遍历生成相应的有向树；(2)对树中每
42、个结点定义两个函数F(i)和G(i)，分别表示以i为根的子树中选择i和不选择i时，该子树的最大节省金额数。另外S(i)表示结点i权值。动态规划方法为：对叶子结点：F(i)=S(i),G(i)=0 对非叶子结点：F(i)=sum(G(j)+S(i),G(i)=sum(max(F(j),G(j)其中j为i的子女，sum表示对各个子树求和。(3)若该树的根为r，则该树的结果为max(F(r),G(r)。,2、解题思路 对于单棵树，可以用动态规划的方法求出结果，方法,3、参考程序,#include#includeusing namespace std;int k,s1001;/商品种类与其节省金额st
43、ruct node/图结点定义 node(int vv=0,node*nn=NULL)v=vv;next=nn;int v;node*next;*g1001;/gi表示第i个结点相邻的结点组成的链表int tag1001;/标记结点是否搜索过没有,1表示已搜索，0则没有int funf1001,fung1001;/深度优先遍历该树并生成相应的有根树void search(int v);/搜索出以v为根生成的有根树int getf(int v);/计算以v为根的子树中选择v时，该子树的最大节省金额数int getg(int v);/计算以v为根的子树中不选择v时，该子树的最大节省金额数,3、参考
44、程序#include,3、参考程序,int main(void)int m,i,v1,v2;int ans=0;memset(g,0,sizeof(g);/每个指针初始化为NULL memset(tag,0,sizeof(tag);memset(funf,-1,sizeof(funf);memset(fung,-1,sizeof(fung);cin k m;/读入商品种类与不能同时购买商品对数 for(i=1;i si;for(i=1;i v1 v2;gv1=new node(v2,gv1);/以插入形成邻接表 gv2=new node(v1,gv2);,3、参考程序int main(void
45、),3、参考程序,/对每个还没有被访问的结点，以该结点为根生成相应的有根树，对/该树用动态规划的方法求解目标函数，并累加起来作为最终答案 for(i=1;i getg(i)?getf(i):getg(i);cout ans;return 0;,3、参考程序/对每个还没有被访问的结点，以该结点为根生成,3、参考程序,void search(int v)/搜索出以v为根生成的有根树/关键是在邻接表中去掉回父结点的边 tagv=1;/对每个相邻的结点 for(node*loop=gv;loop!=NULL;loop=loop-next)/对子女依次循环 if(tagloop-v=0)/该子女没有访问
46、过 node*pre=NULL,*temp;for(temp=gloop-v;temp!=NULL;temp=temp-next)if(temp-v=v)break;/邻结点是父亲，跳出 pre=temp;if(temp)/从break退出/跳过可回到父亲的边(有根树，向下)if(pre=NULL)gloop-v=gloop-v-next;else pre-next=temp-next;search(loop-v);/深度搜索下一层,3、参考程序void search(int v)/搜索出以,3、参考程序,int getf(int v)/计算以v为根的子树中选择v时，该子树的最大节省金额数 i
47、f(funfv=0)/已经计算过 return funfv;funfv=sv;for(node*loop=gv;loop!=NULL;loop=loop-next)funfv+=getg(loop-v);/逐个累加(不选子女)return funfv;int getg(int v)/计算以i为根的子树中不选择i时，该子树的最大节省金额数 if(fungv=0)return fungv;fungv=0;for(node*loop=gv;loop!=NULL;loop=loop-next)fungv+=(getf(loop-v)getg(loop-v)?getf(loop-v):getg(loop-v);/判断子女选好还是不选好 return fungv;,3、参考程序int getf(int v)/计算以v为根的,
