最大化数字乘积

Question

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

解决这个问题的一种方法是列出所有子集，然后找到乘积最大的那个。是否有比暴力更高效的算法？

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

- Anindya Dutta

---

什么是k子集？n1，n2，... nk是某个子集的一部分吗？还是你可以“发明”它们？ - amit

将它们排序，将最大的 k 个数相乘。如果你需要处理负数，那就会变得有点复杂，但只是有点而已。 - High Performance Mark

@amit 对不起，没有 k 个子集。我指的是对于子集 {n1,...nk} 可能产生的所有可能子集。 - Anindya Dutta

我仍然对问题描述感到困惑，抱歉。你有一些数字，需要选择它们的一个子集，满足以下两个条件：(a)符合某些要求，(b)最大化某个目标函数。我认为要求(a)是子集必须加起来等于给定的数字n，但不清楚是否还需要包含恰好给定数量k的数字。 - j_random_hacker

@j_random_hacker 你有一个数字 n。你需要找到 k 个数字，使它们的和等于 n，并且这 k 个数字的乘积是所有这样的 k 个数字集合中最大的。 - Anindya Dutta

Answer 1

最大化乘积n1*n2*..*nk等同于最大化其对数log(n1*n2*..*nk) = log(n1)+log(n2)+ .. +log(nk)，同时满足约束条件n1+..+nk = n

由于对数是一个凹函数，这个最大值将在一个k元组上实现，使得没有两个值相差超过两个（因为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。

- vib

Answer 2

我现在有一个想法。

如果数字为n，并且它能够被k整除，那么我们将得到数字n/k重复出现k次，这使得求和的条件成立。此外，请注意，在这种情况下，当我们使用n/k，其中k完全除n时，结果的乘积将是最大的。如果它不是一个完美的除数，则可以找到ceil(n/k)*k，并将ceil(n/k)乘以k-1次，最后一个整数可以通过n - (ceil(n/k) * (k-1))找到。

假设n_i值可以相同。

编辑

我有一些非常错误的数学知识，但是在这里证明了为什么要使n1和n2相等，对于n1 * n2最大化时，A = n1 + n2。

A = n1 + n2
n2 = A - n1;
P = n1 * n2
P = n1 * (A - n1) = A * n1 - n1^2
对n1微分P
dP/dn1 = A - 2 * n1
要找到拐点，我们需要将dP/dn1 = 0并解决
A - 2 * n1 = 0
n1 = A/2
这表明n1 = A/2，因此n1 = n2
这告诉我们要使P最大化（因为双重微分是负的），我们需要n1 = n2

我认为可以将此证明扩展到k个变量？也许有人可以扩展这个答案。

- phoxis

---

@AnindyaDutta：还在思考中。我认为这应该可以正常工作。但在给出数学证明之前，答案将不完整。 - phoxis

是的，这个运行良好。我也在寻找数学证明。也许我应该把这个问题转到数学堆栈交换。 - Anindya Dutta

@AnindyaDutta，不确定是要移动还是发布一个特定的问题（如果它不存在）。但我认为扩展上面这个答案中的证明以适用于多个变量可能会对您有所帮助。 - phoxis

证明只需从对数的凹性即可得出，无需进行微分（详见我的答案）。 - vib

@vib：是的，需要一点时间才能理解。 - phoxis