动态规划（七）

乘法问题 问题描述：设有1个长度为n的数字字符串，分成k+1个部分，使得k+1个部分的乘积为最大。 [样例]输入： 6 3 n=6, k=3 310143 输出：3720

分析 最优子结构分析 设数字字符串为a1a2…an K=1 时，一个乘号可以插在a1a2…an中的n-1个位置，这样就得到n-1个子串的乘积： a1*a2…an, a1a2*a3…an, …, a1a2…a n-1*an 此时的最大值= max{a1*a2…an, a1a2*a3…an, …, a1a2…a n-1*an } K=2时，二个乘号可以插在a1a2…an中n-1个位置的任两个地方，这样总共会产生 个乘积。把这些乘积分个类，便于观察规律。 Case1: a1a2 …*a n-1*an , a1a2 …*a n-2 a n-1*an , a1*a2 …a n-3 a n-2 a n-1*an , 因后一个乘号位置不变，要使这些乘积最大，就要找出在前n-1个数中插入一个乘号的最大值。设符号F[n-1,1]为在前n-1个数中插入一个乘号的最大值,则 Case1的最大值为F[n-1,1]*an

分析 Case2: a1a2 …*a n-2*a n-1 an , a1a2 …*a n-3 a n-2* a n-1 an , a1*a2 …a n-3 a n-2* a n-1 an , 因后一个乘号位置不变，要使这些乘积最大，就要找出在前n-2个数中插入一个乘号的最大值。设符号F[n-2,1]为在前n-2个数中插入一个乘号的最大值,则 Case2的最大值为F[n-2,1]*a n-1 an 同理，Case3的最大值为F[n-3,1]* a n-2 a n-1 an …… Case n-2的最大值为F[2,1]*a3…an

分析 下面以n=9, k=4, s=‘321044105’为例，说明计算过程。 n 1 2 3 4 5 6 7 8 9 1 - 6 63 630 12840 128416 - - - 2 - - 6 60 2520 51360 526440 - - 3 - - - 0 240 10080 103320 1033200 - 4 - - - - 0 960 10080 100800 5166000 其实在上面显示的计算过程中，我们未显示出右子串是什么，但它实际上是要参加运算的。我们引入符号f[i,s]表示从a1~aj中插入s个乘号取得的最大值，g[I,j]表示从ai~aj的子串的数值。则上式可表示为： f[9,4] = max{f[8,3]*g[9,9], f[7,3]*g[8,9], f[6,3]*g[7,9], f[5,3]*g[6,9], f[4,3]*g[5,9]} F[8,3] = max{f[7,2]*g[8,8], f(6,2]*g[7,8], f[5,2]*g[6,8], f[4,2]*g[5,8],f[3,2]*g[4,8]} F[7,3] = max{f[6,2]*g[7,7], f[5,2]*g[6,7], f[4,2]*g[5,7], f[3,2]*g[4,7]} …… F[7,2] = max{f[6,1]*g[7,7], f[5,1]*g[6,7], f[4,1]*g[5,7], f[3,1]*g[4,7], f[2,1]*g[3,7]} F[6,1] = max {f[5,0]*g[6,6], f[4,0]*g[5,6], f[3,0]*g[4,6], f[2,0]*g[3,6], f[1,0]*g[2,6]}

分析 上面的分析已经看出问题的最优子结构性质。下面是递归地定义问题的最优解。 F[I,j] = max{f[I-1,j-1]*g[I,I], f[I-2,j-1]*g[I-1,I], f[I-3,j-1]*g[I-2,I], …., f[j,j-1]*g[j+1,I]} (1<=I<=n, 1<=j<=k) 上式的边界条件是什么？ f[I,0] =g[1,I] (1<=I<=n) 我们要求的问题的最优解是f[n,k].

分析 阶段：我们看到在f[n,k]中有二个自变量，到底选择哪个作为阶段变量呢？ 由于子问题是在子串中插入k-1,k-2, …,1,0个乘号，因此，把k作为阶段变量。 阶段数J为1~k，表示在子串中插入J个乘号。 初始阶段为k=0，表示在子串中插入0个乘号。这也就是上面分析过的边界条件： f[I,0] =g[1,I] (1<=I<=n) 想一想，怎样用程序段实现这个初始阶段？ for I:= 1 to n do f[I,0] := g[1, I];

分析 状态数分析 状态数分析是本题的难点。但对题意作深入理解后，就会逐渐理解状态数该如何确定。请记住，状态变量是阶段变量的函数，它会随着阶段变量的改变而变化。 阶段数J ，表示在子串中插入J个乘号。那么最少是多长的子串才能刚好插入这J个乘号呢？ 应该是长度为J+1的子串。这就是J阶段的起始状态：在长度为J+1的子串中插入I个乘号。 再思考状态数的上界。最长允许的子串是多少呢？请记住还有k-J个乘号需要插入右子串中。 与上面类似，右子串最短刚好容纳K-J个乘号的长度为K-J+1，而整个字串的长度为n，故左子串最长允许的长度为n-(k-J+1) = n+J-k-1 总结起来，状态数I的取值范围就是J+1 <= I <= n+J-k-1

分析 决策数分析 阶段、状态确定了，要求解的当前问题也就确定了：在长度为I的子串中插入J个乘号的最优解是多少？用符号表示就是求F[I,J]的值。 前面已经分析过，这一问题可以理解为用第J个乘号把长度为I的字串分左、右二个子串，左子串中插有J-1个乘号，求得它的最优解，再乘以右子串的问题。与状态数分析相似的问题又来了：这第J个乘号可以放在长度为I的字串的哪些位置呢？ 由于左子串要插入J-1个乘号，因此左子串的最短长度为J-1+1 = J，这就是决策变量的起始值，也就是下界。 由于第J个乘号一定要分出左右子串来，右子串最短为1，此时左子串最长为I-1，这就是决策变量的终值，也就是上界。 总结起来，决策变量的取值范围是：J<= p <= I-1

分析 做什么决策？ 求f[I,J]的决策。 前边分析过： F[I,j] = max{f[I-1,j-1]*g[I,I], f[I-2,j-1]*g[I-1,I], f[I-3,j-1]*g[I-2,I], …., f[j,j-1]*g[j+1,I]} 我们看到左子串的长度在变化，用决策变量P代替，上式变为： f[I,j] = max{f[p,j-1]*g[p+1,I]} (J<= p <= I-1) 这个熟悉的数学式大家知道该怎样转化成for循环结构了吧。

分析 G[I,j]的处理 G[I,J]的定义是从字串的ai~aj的数值。没有现成的方法可以把一个字符串转换成一个长整型数据。因此需要我们自行定义函数。数字字符转化为对应整数的方法是利用求序号函数ORD，它可以求出字符的ASCII码： ORD(‘5’) - ORD(‘0’) = 5 ORD(‘9’) - ORD(‘0’) = 9 将一个数字字串转化为对应的整数的代码段是： d := 0; for I:= 1 to Length(str) do d := d * 10 + ord(str[I]) – ord(‘0’); {str是字符串类型，也可以看成字符数组} 下面是定义函数g(I,j)的代码： Function g(str:string; I,j:integer):longint; {从str中取出ai~aj的数字} Var d : longint; k : integer; Begin for k := I to j do d := d * 10 + ord(str[k]) – ord(‘0’); g := d; End;

分析 注意程序中用到的变量的数据类型的选择。 数组f[1..n, 0..k] 应是什么类型？ 注意凡是程序中出现的用于保存f[I,j]值的工作变量都应与它的类型一致。

练习 请自行完成程序。 请思考本题输入的数字字符串的长度限制是多少？ 如果要处理比长整型长得多的数字字符串，程序要作哪些修改？

进一步编程题 加法问题。 数值范围（5<=N<=40，1<=K<=20，k<n) [样例]输入： 79846 2 输出： 133 输入： 82363983742 3 输出：2170

进一步编程题 乘积最大 (NOIP 2000第二题) 问题描述: 今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目: 设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串: 312，当N=3，K=1时会有以下两种分法： 1）3*12=36 2）31*2=62 这时，符合题目要求的结果是： 31*2=62 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

进一步编程题 输入： 程序的输入共有两行: 第一行共有2个自然数N,K (6<=N<=40，1<=K<=6) 第二行是一个K度为N的数字串。 输出: 结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 样例: 输入 4 2 1231 输出 62

进一步编程题 求函数最大值 已知3个函数A，B，C值如下表示，自变量取值为0~10的整数。请用动态规划的方法求出一组x，y，z，使得A(x)+B(y)+C(z)为最大，并且满足x2+y2+z2<N，N由键盘输入。 X 0 1 2 3 4 5 6 7 8 9 10 A(x) 2 4 7 11 13 15 18 22 18 15 11 B(x) 5 10 15 20 24 18 12 9 5 3 1 C(x) 8 12 17 22 19 16 14 11 9 7 4