c++ 那边有人问了个题，我不会，在这边求个方法。

设有一个长度为N的数字串，要求使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

用f[i,j]表示前i个数字，其中加入k个乘号，组成的乘机最大的数组，边界条件f[i,0]=原本数;

f[i,j]=MAX（f[k,j-1]*(由第k+1到i组成的数)） j<=k<=i-1

应该要用大数运算来做

f(i, j) 的 j 表示什么？另外每个 f(i, j) 都是个数组是吧？

原来几乎就是穷举。c++ 那边有个人瞎答了个类似分治的算法，搞的我想了半天也没想通。


[ 本帖最后由 pangding 于 2012-6-23 22:25 编辑 ]

写错了，插入j个乘号

是个不错的答案。我等一天，明天结帖。

怎么会是穷举啊，有n^2个f状态要求，每个状态求个过程枚举n次，总的时间复杂度是O(N^3)，大数运算不计

穷举的复杂度是C(n-1,k），这个没可比性啊

嗯，我说的不太专业。应该叫动态规划。
当然算过的地方不用再算了，我当时的穷举意思是每每多加一个乘号，就得把所有可能插乘号的地方试遍。能用的性质只有 a*b，当 b 不变的时候，a 越大积越大而已。

动态规划肯定能解这个问题。不过直觉告诉我，这个问题可能能用贪心算法。关于这个目前我没有完全证明，只是直觉

关于这个问题，我的第一反应是如何绕开大数运算。因为它本身就是个编码复杂、效率低下的算法。基础方法的效率是O(n^2)，而目前我知道的最有效的方法也需要O(n^1.6)，且代码要复杂很多。

设串为A，长度为N。那么这个串的数值可以表示为

0.A * 10^N （举个例子，对于串123，其数值可以表示为0.123 * 10^3）

如果将A从第i位与第i+1位之间分开成两部分B、C。那么这两部分的乘积可表示为

0.B * 10^i * 0.C * 10^(N-i)

= 0.B * 0.C * 10^N

由此可见，影响B、C的乘积大小的因素是0.B和0.C的大小，而不是它们的长短。

而0.B、0.C的大小比较是等同于字符串的比较的。也就是说，靠近左侧的数字越大这个小数的值就越大。

所以我们可以先找出串中所有最大数字（一位）出现的位置（不包括串的首位）及数量（设为T）。

如果T = K，那么就直接在这些位置的前面插入乘号即完成任务。

如果T < K，那么可以肯定的是这些位置前面是必须要插入乘号的，之后在找出串中次大的数字出现的位置及数量，重复上述过程。

如果T > K，那么需要将这T个串合并成K个。如何合并？这是我还没有想清楚的部分。

将最小的串与前一串合并？如果有多个相等的最小串又该如何合并？等等等等

呵呵，如果能找到一个合并最优合并策略，并要达到局部最优等价于整体最优的程度，那以这个问题就可以应用贪心算法了。

如果找不到，我想也应该在这部分应用动态规划来解决这个子问题。一来问题规模被缩小了，二来运算手段简单了。

希望我这块砖能敲开各位思想的大门，引出美玉来

我昨天也觉得这个题可能有类似贪心法的算法，但确实有些问题很难处理。

比如 198910 加两个乘号：
1 * 98 * 910 = 89180 < 19 * 8 * 910 = 138320

而且还有类似这样的例子：
999999 加一个乘号答案应该是： 999 * 999；而加两个，却是 99 * 99 * 99。
所以合并分点的位置，也需要从全局考虑。局部最优解可能不能推到整体最优。

[ 本帖最后由 pangding 于 2012-6-24 10:44 编辑 ]

这个问题，好多算法还没学，不过用高中的排列组合中的，插板法可以解决，具体的K+1部分，用K个循环解决，循环是还可以优化的，例遍所有的可能组合，然后比较那种组合的结果最大。请大家指教！

收到的鲜花

• pangding 于 2012-06-25 23:18 送鲜花  20朵   附言：感谢回帖