C案例04动态规划.ppt

2019/7/26,1,第四讲,动态规划 （Dynamic programming）,2019/7/26,2,一、经典问题：数塔问题,有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。,2019/7/26,3,用暴力的方法，可以吗？,2019/7/26,4,这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（230= 10243 109=10亿）。,试想一下：,2019/7/26,5,拒绝暴力，倡导和谐,2019/7/26,6,从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。 同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。 如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。 结论：自顶向下的分析，自底向上的计算。,考虑一下：,2019/7/26,7,思路：从倒数第二行起， 按照状态转移方程 dpij = max(dpi + 1j, dpi + 1j + 1) + valij 向上递推， 直到val11， 此时dp11就是结果,2019/7/26,8,二、经典问题：最长有序子序列,问题描述 找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列 （注：这里有序指非递减顺序，且不要求子序列连续）。 例如，对于序列3, 7, 1, 5, 9, 3，其中最长有序子序列长度为3，这样的子序列有： 3, 7, 9、1, 5, 9、3, 5, 9。,2019/7/26,9,二、经典问题：最长有序子序列,2019/7/26,10,二、经典问题：最长有序子序列,2019/7/26,11,二、经典问题：最长有序子序列,2019/7/26,12,三 1160 FatMouses Speed,Problem Description FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing. Input Input contains data for a bunch of mice, one mouse per line, terminated by end of file. The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice. Two mice may have the same weight, the same speed, or even the same weight and speed.,2019/7/26,13,三 1160 FatMouses Speed,Output Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m1, m2,., mn then it must be the case that Wm1 Sm2 . Smn In order for the answer to be correct, n should be as large as possible. All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.,2019/7/26,14,三 1160 FatMouses Speed,Sample Input 6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900,Sample Output 4 4 5 9 7,2019/7/26,15,三 1160 FatMouses Speed,解题思路： 题目要求找到的体重递增，速度递减 老鼠，先把老鼠的体重进行升序排序 然后算出速度的最长递减子序列。,2019/7/26,16,四 1087 Super Jumping! Jumping! Juping!,Problem Description Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now. The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path. Your task is to output the maximum value according to the given chessmen list.,2019/7/26,17,四 1087 Super Jumping! Jumping! Juping!,Input Input contains multiple test cases. Each test case is described in a line as follow: N value_1 value_2 value_N It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int. A test case starting with 0 terminates the input and this test case is not to be processed. Output For each case, print the maximum according to rules, and one line one case.,2019/7/26,18,四 1087 Super Jumping! Jumping! Juping!,Sample Input 3 1 3 2 4 1 2 3 4 4 3 3 2 1 0 Sample Output 4 10 3,解题思路？,找序列中最大升序子序列的和,2019/7/26,20,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,算法总体思想,2019/7/26,21,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,算法总体思想,2019/7/26,22,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,算法总体思想,T(n),2019/7/26,23,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。,2019/7/26,24,动态规划算法的基本要素,一、最优子结构,问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,2019/7/26,25,动态规划算法的基本要素,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,2019/7/26,26,动态规划算法的基本要素,三、备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,int LookupChain(int i，int j) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; ,2019/7/26,27,五、经典问题：最长公共子序列,Problem Description A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = another sequence Z = is a subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1,2,.,k, xij = zj. For example, Z = is a subsequence of X = with index sequence . Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y. The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.,2019/7/26,28,五、经典问题：最长公共子序列,HDOJ-1159： Sample Input abcfbc abfcab programming contest abcd mnp,Sample Output 4 2 0,2019/7/26,29,最长公共子序列,若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,2019/7/26,30,最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则 (1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。 (2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。 (3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,2019/7/26,31,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,2019/7/26,32,辅助空间变化示意图,2019/7/26,33,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; ,构造最长公共子序列 void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); ,2019/7/26,34,算法的改进,在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。,2019/7/26,35,六、经典问题：1421 搬寝室,Problem Description 搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.,2019/7/26,36,六、经典问题：1421 搬寝室,Input 每组输入数据有两行,第一行有两个数n,k(2=2*k=n2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于215的正整数). Output 对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.,2019/7/26,37,六、经典问题：1421 搬寝室,Sample Input 2 1 1 3 Sample Output 4,2019/7/26,38,第一感觉：,根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？,证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可： (a-b)2+(c-d)2 (a-c)2+(b-d)2 (a-b)2+(c-d)2 (a-d)2+(b-c)2 (略),2019/7/26,39,预备工作：,排序！,2019/7/26,40,第二感觉：,对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？ 请思考,考虑以下情况： 1 4 5 8,什么结论？,2019/7/26,41,详细分析：,从最简单的情况考虑： 2个物品选一对，结论显然,结论？,4个物品选一对？（如何利用前面的知识）,3个物品选一对，,n个物品选一对，,最终问题：n个物品选k对（n=2k） ，如何？,n个物品选二对，,2019/7/26,42,解题思路,先对物品的重量进行排序，取相邻的物品，将相邻的物品的差的平方另外存储，得到状态转移方程：dpij=min(dpi-1j,dpi-2j-1+si), si是代表i,i+1这两个物品的疲惫度. 因为si-1,si.代表的是ai-1,ai,ai+1的疲惫度，中间共享了一个ai，所以第二项要用dpi-2.,2019/7/26,43,参考代码,#include #include using namespace std; #define INF 0x7fffffff int dp20002000,a2000,s2000; int main() int n,k,i,j; while( scanf(“%d%d“, ,2019/7/26,44,七、经典问题：1058 Humble Numbers,Problem Description A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, . shows the first 20 humble numbers. Write a program to find and print the nth element in this sequence,2019/7/26,45,七、经典问题：1058 Humble Numbers,Input The input consists of one or more test cases. Each test case consists of one integer n with 1 = n = 5842. Input is terminated by a value of zero (0) for n. Output For each test case, print one line saying “The nth humble number is number.“. Depending on the value of n, the correct suffix “st“, “nd“, “rd“, or “th“ for the ordinal number nth has to be used like it is shown in the sample output.,2019/7/26,46,七、经典问题：1058 Humble Numbers,2019/7/26,47,算法分析：典型的DP!,1 -?,1 -2=min(1*2,1*3,1*5,1*7),1 -2 -3=min(2*2,1*3,1*5,1*7),1 -2 -3 - 4 = min(2*2,2*3,1*5,1*7),1 -2 -3 - 4 -5= min(3*2,2*3,1*5,1*7),2019/7/26,48,状态转移方程？,F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7) (ni,j,k,m) 特别的： i,j,k,m 只有在本项被选