java - 寻找最大乘积的算法方法

Question

如果给出 2 个整数，请说 a 和 b。找到 b 个正整数，使得它们的和等于 a，并且它们的乘积最大。我们必须返回最大乘积作为输出。

约束是 -

0<=b<=20

b<=a<=100

必须使用什么样的算法或方法来解决这个问题？

Answer 1

假设我们有两个整数 x,y 使得 x < y。

(x+1)*(y-1) = x*y + y - x - 1 >= x*y

这就是说我们可以通过增加 x 和减小 y 来使产品变大。

因此最佳答案将使所有数字彼此相差在 1 个单位以内(否则我们可以获得更好的答案)。

所以我们的数字都等于 x 或 x+1(对于某些 x 尚未确定)。假设我们有 k 个较大的数字，我们知道必须有 b-k 个较小的数字。我们现在可以按如下方式计算 x 和 k:

x*(b-k)+k*(x+1) = a
b*x - k*x + k*x + k = a
b*x + k = a

因此 x = a//b 和 k = a % b。

最终的产品将是 x**(b-k)*(x+1)**k。

(请注意，如果 sum 等于 a 且 b > a，这个问题似乎有些奇怪，因为这不可能用正整数实现。)