理学动态规划基础讲解及经典案例分析解答课件

第九课 动态规划(I) 综合实践考核 2018/12/261 数字三角形 1、问题描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条 不同的路径。对于每条路径，把路径上面的数加起来可以得到 一个和，和最大的路径称为最佳路径。你的任务就是求出最佳 路径上的数字之和。 注意：路径上的每一步只能从一个数走到下一层上和它最近的 左边的数或者右边的数。 问题描述 输入数据 输入的第一行是一个整数N (1 #define MAX_NUM 100 int 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 ) return nSum1+Drj; return nSum2+Drj; 3、参考程序 I int main(void) int m; scanf(“%d“, for( int i = 1; i #include #define MAX_NUM 100 int 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( aMaxSumr+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 int main(void) int m; scanf(“%d“, /将 aMaxSum 全部置成-1, 开始时所有的 MaxSum(r, j)都没有算过 memset(aMaxSum, -1, sizeof(aMaxSum); for( int i = 1; i 1 ; i - ) for( j = 1; j aMaxSumij+1 ) aMaxSumi-1j = aMaxSumij + Di-1j; else aMaxSumi-1j = aMaxSumij+1 + Di-1j; printf(“%d“, aMaxSum11); return 0; 思考题：上面的几个程序 只算出了最佳路径的数字 之和。如果要求输出最佳 路径上的每个数字，该怎 么办？ 动态规划解题的一般思路 n 许多求最优解的问题可以用动态规划来解决。 n 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导 致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就 要被保存，所以每个子问题只需求解一次。 n 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模 从原来的n 变成了n-1，或从原来的nm 变成了n(m-1) 等 等。 n 找到子问题，就意味着找到了将整个问题逐渐分解的办法。 n 分解下去，直到最底层规模最小的的子问题可以一目了然地看出 解。 n 每一层子问题的解决，会导致上一层子问题的解决，逐层向上， 就会导致最终整个问题的解决。 n 如果从最底层的子问题开始，自底向上地推导出一个个子问题的 解，那么编程的时候就不需要写递归函数。 动态规划解题的一般思路 n 用动态规划解题时，将和子问题相关的各个变量的一组取值 ，称之为一个“状态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的 解。 n 比如数字三角形，子问题就是“从位于(r，j)数字开始，到底 边路径的最大和”。这个子问题和两个变量r 和j 相关，那么一 个“状态”，就是r, j 的一组取值，即每个数字的位置就是一个“ 状态”。该“状态”所对应的“值”，就是从该位置的数字开始， 到底边的最佳路径上的数字之和。 n 定义出什么是“状态”，以及在该 “状态”下的“值”后，就要找 出不同的状态之间如何迁移即如何从一个或多个“值”已知 的 “状态”，求出另一个“状态”的“值”。状态的迁移可以用递推 公式表示，此递推公式也可被称作“状态转移方程”。 动态规划解题的一般思路 n用动态规划解题，如何寻找“子问题”，定义“状态”，“状态转 移方程”是什么样的，并没有一定之规，需要具体问题具体分 析，题目做多了就会有感觉。 n甚至，对于同一个问题，分解成子问题的办法可能不止一种 ，因而“状态”也可以有不同的定义方法。不同的“状态”定义方 法可能会导致时间、空间效率上的区别。 最长上升子序列 1、问题描述 一个数的序列bi，当b1 bj ) if( nTmp #include #include #define MAX_N 1000 #define INFINITE 1000000 int t, n, x, y, max; struct Platform int Lx, Rx, h; ; Platform aPlatformMAX_N + 10; int 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、参考程序 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;i = x) break; if( i max )/太高 return INFINITE; 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( aRightMinTimei = -1 ) aRightMinTimei = MinTime(i, false); nLeftTime += aLeftMinTimei; nRightTime += aRightMinTimei; if( nLeftTime 是序列X = 的子序列当且仅当存在严格上升的序列 ，使得对j = 1, 2, . ,k, 有xij = zj。比如Z = 是X = 的子序列。 现在给出两个序列X 和Y，你的任务是找到X 和Y 的最大公共 子序列，也就是说要找到一个最长的序列Z，使得Z 既是X 的 子序列也是Y 的子序列。 输入数据 输入包括多组测试数据。每组数据包括一行，给出两个长度不 超过200 的字符串，表示两个序列。两个字符串之间由若干个 空格隔开。 问题描述 输出要求 对每组输入数据，输出一行，给出两个序列的最大公共子序 列的长度。 输入样例 abcfbc abfcab programming contest abcd mnp 输出样例 4 2 0 2、解题思路 n用字符数组s1、s2存放两个字符串，用s1i表示s1中的第i 个字符，s2j表示s2中的第j个字符（字符编号从1 开始）， 用s1i表示s1的前i个字符所构成的子串，s2j表示s2的前j个字 符构成的子串，MaxLen(i,j)表示s1i 和s2j 的最长公共子序列 的长度，那么递推关系如下： nif( i =0 | j = 0 ) n MaxLen(i, j) = 0 /两个空串的最长公共子序列长度是0 nelse if( s1i = s2j ) n MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1; nelse n MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j); 2、解题思路 n 显然本题目的“状态”就是s1 中的位置i 和s2 中的位置j。 n “值”就是MaxLen(i, j)。 n 状态的数目是s1 长度和s2 长度的乘积。可 以用一个二维数组来存储各个状态下的“值”。 n 本问题的两个子问题，和原问题形式完全一 致的，只不过规模小了一点。 3、参考程序 #include #include #define MAX_LEN 1000 char sz1MAX_LEN; 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 nLen2 ) aMaxLenij = nLen1; else aMaxLenij = nLen2; printf(“%dn“, aMaxLennLength1nLength2); return 0; 陪审团的人选 1、问题描述 在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定 。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪 审团的候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是： 控方和辩方会根据对候选人的喜欢程度，给所有候选人打分 ，分值从0 到20。为了公平起见，法官选出陪审团的原则是： 选出的m 个人，必须满足辩方总分和控方总分的差的绝对值最 小。如果有多种选择方案的辩方总分和控方总分的之差的绝对 值相同，那么选辩控双方总分之和最大的方案即可。最终选出 的方案称为陪审团方案。 问题描述 输入数据 输入包含多组数据。每组数据的第一行是两个整数n 和m，n 是候选人数目，m 是陪审团人数。注意，1 #include #include int f301000; int Path301000; int P300; /控方打分 int D300; /辩方打分 int Answer30; /存放最终方案的人选 int CompareInt(const void * e1, const void * e2) return * (int *) e1) - * (int *) e2); 3、参考程序 int main(void) int i, j, k; int t1, t2; int n, m; int nMinP_D; /辩控双方总分一样时的辩控差 int nCaseNo;/测试数据编号 nCaseNo=0; scanf(“%d%d“, while(n+m) nCaseNo+; for(i=1;i=0) /方案 f(j, k)可行 for(i=1;ifj+1k+Pi-Di) /即时判别记住更合适的f(j,k) t1=j; t2=k; while(t10 t1-;/减少1人 if(t1=0) /没有发现 fj+1k+Pi-Di=fjk+Pi+Di; Pathj+1k+Pi-Di=i; 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 #include using namespace std; int k, s1001;/商品种类与其节省金额 struct 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、参考程序 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、参考程序 /对每个还没有被访问的结点，以该结点为根生成相应的有根树，对 /该树用动态规划的方法求解目标函数，并累加起来作为最终答案 for(i=1; i getg(i) ? getf(i) : getg(i); cout next)/对子女依次循环 if(tagloop-v