CODEWITHSUNDEEP
algorithmmath
Anindya Dutta
Anindya Dutta

Reputation: 1982

Maximize product of numbers

Given a number n and partition value k, such that n1+n2+..nk=n, I need to find the set {n1,n2..,nk} such that n1*n2*...nk is maximum.

One method of solving this would be listing out all the subsets and then finding the one with the maximum product. Is there any algorithm that is efficient (anything better than brute force)?

To find subsets, this formula can be used and I am currently developing using this logic.

Upvotes: 4

Views: 4657

Answers (2)

vib
vib

Reputation: 2274

Maximizing the product n1*n2*..*nk is equivalent to maximizing its logarithm log(n1*n2*..*nk) = log(n1)+log(n2)+ .. +log(nk), subject to the constraint n1+..+nk = n

Because the logarithm is a concave function, this maximum will be attained on a k-uplets such that no two values differ by more than two (because log((a+b)/2) >= (log(a)+log(b))/2. This implies that, defining x = floor(n/k), you can restrict yourself to the case where each n_i belongs to {x,x+1}.

This further implies that you can determine exactly the subset: if you let a be such that a*x+(k-a)*(x+1) = n, then the maximal subset will be a permutation of
n1 = x, n2 = x, .., n_a = x, n_{a+1} = x+1, .., nk = x+1.
The equation on a can be explicitly solved and yields a = k*(ceil(n/k))-n.

Upvotes: 14

phoxis
phoxis

Reputation: 61940

Here is one idea I am having now.

If the number is n, and if it is perfectly divisible by k, then we have the number n/k occurring k times, which makes the condition for the sum valid. Also, notice that in this case when we use n/k where k divides n perfectly the result of the multiplication of the result will be maximum. If it is not a perfect divisor, then we can find ceil(n/k)*k and multiply ceil(n/k) k-1 times and the last integer can be found by n - (ceil(n/k) * (k-1)).

Assuming the n_i values can be same.

EDIT

I have some very broken math, but here is a proof why to make n1 and n2 will have to be equal, for n1 * n2 maximum when A = n1 + n2.

A = n1 + n2
n2 = A - n1;

P = n1 * n2
P = n1 * (A - n1) = A * n1 - n1^2

Differentiating P with respect to n1

dP/dn1 = A - 2 * n1 

To find the inflection point, we do dP/dn1 = 0 and solve

A - 2 * n1 = 0
n1 = A/2

which indicates n1 = A/2 and therefore n1 = n2

Which tells to make to make P maximum (as the double differentiation is negative), we need to have n1 = n2

I think this proof can be extended to k variables? Maybe someone can extend this answer.

Upvotes: 3

Related Questions