algorithm - 最大化数字的乘积

Question

给定一个数 n 和分区值 k，使得 n1+n2+..nk=n，我需要找到集合{n1,n2..,nk} 使得 n1*n2*...nk 最大。

解决此问题的一种方法是列出所有子集，然后找到具有最大乘积的子集。是否有任何有效的算法(比蛮力更好的算法)？

要查找子集，可以使用此公式，我目前正在使用 this 进行开发逻辑。

Answer 1

最大化乘积 n1*n2*..*nk 等价于最大化它的对数 log(n1*n2*..*nk) = log(n1)+log(n2 )+ .. +log(nk)，受约束 n1+..+nk = n

因为对数是一个凹函数，这个最大值将在 k-uplets 上获得，这样两个值的差异不会超过两个(因为 log((a+b)/2) >= (log (a)+log(b))/2。这意味着，定义 x = floor(n/k)，您可以将自己限制在每个 n_i 属于 {x,x+1}。

这进一步意味着您可以准确地确定子集:如果您让 a 满足 a*x+(k-a)*(x+1) = n，那么最大子集将是
的排列n1 = x, n2 = x, .., n_a = x, n_{a+1} = x+1, .., nk = x+1.
a 上的方程可以显式求解并得出 a = k*(ceil(n/k))-n。