首页 > 代码库 > 插入乘号问题(DP)
插入乘号问题(DP)
一、问题提出
在一个由n个数字组成的数字串中插入r个乘号(1<=r<n<16),将它分成r+1个整数,找出一种乘号的插入方法,使得r+1个整数的乘积最大。
例如,对给定的数串847313926,如何插入r=5个乘号,使其积最大?
当给定乘号数量时首先考虑以枚举解题:
例如在7个数字之间插入三个乘号
#include<iostream> #include<string> using namespace std; string str; int s[10]; int t[10],father[10]; int main() { int i,j,count=1; _int64 d,y,ans=0; cin>>str; int k=str.length(); for(i=0;i<k;i++) s[i+1]=str[i]-'0'; t[0]=0;t[4]=7; for(t[1]=1;t[1]<=4;t[1]++) for(t[2]=t[1]+1;t[2]<=5;t[2]++) for(t[3]=t[2]+1;t[3]<=6;t[3]++) { y=1; for(i=0;i<=3;i++) { d=0; for(j=t[i]+1;j<=t[i+1];j++) d=d*10+s[j]; y*=d; } if(ans<y) { ans=y; for(i=1;i<4;i++) father[i]=t[i]; } } printf("分别插入到%d %d %d之后!!!最大值为%lld\n",father[1],father[2],father[3],ans); return 0; }
对于一般插入r个乘号,采用穷举已不适合。注意到插入r个乘号是一个多阶段决策问题,应用动态规划来求解是适宜的。
二、动态规划设计
1.建立递推关系
设f(i,k)表示在前i位数中插入k个乘号所得乘积的最大值,a(i,j)表示从第i个数字到第j个数字所组成的j-i+1(i<=j)位整数值。
为了寻求递推关系,先看一个实例:对给定的847313926,如何插入r=5个乘号,使其乘积最大?我们的目标是为了求取最优值f(9,5)。
①设前8个数字中已插入4个乘号,则最大乘积为f(8,4)*6;
②设前7个数字中已插入4个乘号,则最大乘积为f(7,4)*26;
③设前6个数字中已插入4个乘号,则最大乘积为f(6,4)*926;
④设前5个数字中已插入4个乘号,则最大乘积为f(5,4)*3926;
比较最大值即为f(9,5)。
依此类推,为了求f(8,4):
①设前7个数字中已插入3个乘号,则最大乘积为f(7,3)*2;
②设前6个数字中已插入3个乘号,则最大乘积为f(6,3)*92;
③设前5个数字中已插入3个乘号,则最大乘积为f(5,3)*392;
④设前4个数字中已插入3个乘号,则最大乘积为f(4,3)*1392;
比较以上4个数值的最大值即为f(8,4)。
一般地,为了求取f(i,k),考察数字串的前i个数字,设前j(k<=j<i)个数字中已插入k-1个乘号的基础上,在第j个数字后插入第t个乘号,显然此时的最大乘积为f(j,k-1)*a(j+1,i)。于是可以得递推关系式:
f(i,k)=max(f(j,k-1)*a(j+1, i)) (k<=j<i)
前j个数字没有插入乘号时的值显然为前j个数字组成的整数,因而得边界值为:
f(j,0)=a(1,j) (1<=j<=i)
为简单计,在程序设计中省略a数组,用变量d替代。
2.递推计算最优值
for (d = 0, j = 1; j <= n; j++) { d = d * 10 + b[j - 1]; // 输入数字串每一位赋值给b数组 f[j][0] = d; // 计算初始值f[j][0] } for (k = 1; k <= r; k++) { for (i = k + 1; i <= n; i++) for (j = k; j < i; j++) { for (d = 0, u = j + 1; u <= i; u++) d = d * 10 + b[u - 1]; // 计算d即为a(j+1,i) if (f[i][k] < f[j][k - 1] * d) // 递推求取f[i][k] f[i][k] = f[j][k - 1] * d; } }
3.构造最优解
为了能打印相应的插入乘号的乘积式,设置标注位置的数组t(k)与c(i,k),其中c(i,k)为相应的f(i,k)的第k个乘号的位置,而t(k)标明第k个乘号“*”的位置,例如,t(2)=3,表示第2个“*”号在第3个数字后面。
当给数组元素赋值f(i,k)=f(j,k-1)*d时,作相应赋值c(i,k)=j,表示f(i,k)的第k个乘号的位置是j。在求得f(n,r)的第r个乘号位置t(r)=c(n,r)=j的基础上,其他t(k) (1<=k<=r-1)可应用下式逆推产生:
t(k)=c(t(k+1),k)
根据t数组的值,可直接按字符形式打印表面积所求得的插入乘号的乘积式。
// 在一个数中插入r个乘号,使其积最大 // 利用动态规划求解 #include <stdio.h> #include <string.h> int main() { char numStr[16]; int i, j, k, len, u, r, b[16], t[16], c[16][16]; double f[17][17], d; printf("请输入整数:"); scanf("%s", numStr); printf("请输入插入的乘号个数r: "); scanf("%d", &r); len = strlen(numStr); if (len <= r) { printf("输入的整数位够数不够或r太大!/n"); return 0; } printf("在整数%s中插入%d个乘号,使乘积最大:/n", numStr, r); for (d = 0, j = 0; j <= len - 1; j++) b[j] = numStr[j] - '0'; for (d = 0, j = 1; j <= len; j++) { d = d * 10 + b[j - 1]; // 把b数组的一个字符转化为数值 f[j][0] = d; // f[j][0]赋初始值 } for (k = 1; k <= r; k++) for (i = k + 1; i <= len; i++) for (j = k; j < i; j++) { for (d = 0, u = j + 1; u <= i; u++) d = d * 10 + b[u - 1]; if (f[i][k] < f[j][k - 1] * d) { f[i][k] = f[j][k - 1] * d; c[i][k] = j; } } t[r] = c[len][r]; for (k = r - 1; k >= 1; k--) t[k] = c[t[k + 1]][k]; // 逆推出第k个*号的位置 t[0] = 0; t[r + 1] = len; for (k = 1; k <= r + 1; k++) { for (u = t[k - 1] + 1; u <= t[k]; u++) putchar(numStr[u - 1]); // 输出最优解 if (k < r + 1) putchar('*'); } printf("=%.0f/n", f[len][r]); // 输出最优值 return 0; }代码选自<<趣味编程100>>
部分内容来自http://blog.csdn.net/jqmczx/article/details/6403854。
插入乘号问题(DP)