CODEWITHSUNDEEP
pythonalgorithmoptimizationmodelingmathematical-optimization
Paul Miles
Paul Miles

Reputation: 39

A variation of "How to find the maximum area of a rectangle given its perimeter" with Python

I have an optimization problem with the following mathematical model. It is similar to finding the maximum area of a rectangle given its perimeter but in this example we don't have 2 variables.

I have X number of positive integers whose sum is Y. How can I find the set of integers that will give me the maximum of their multiplications given Y?

Example:

Given that Y = 8 the answer should be X[1] = 2; x[2] = 3; x[3] = 3 since that will give me the maximum of multiplications.

Any python code/logic for this kind of problem?

Upvotes: 2

Views: 766

Answers (3)

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8711

It is true that the “maximum of multiplications will be when all the values are nearest to equal values”, as stated in a previous answer and implemented via
max_list = [s//n] * (n - s%n) + [s//n + 1] * (s%n)
in another answer. This can be justified by techniques similar to those used in proving the arithmetic-mean to geometric-mean inequality, as in (for example) Proof by Pólya.

When the sum Y is given but not the number of terms X, and it's desired to compute X, observe that pow(W,Y/W) is maximal when W = e ≃ 2.71828. The integer nearest to e is 3, so to maximize the product, include mostly 3's, and one or two 2's. In general, include two 2's when Y%3 is 1, and one 2 when Y%3 is 2, and none when Y%3 is 0, and make up the difference with 3's. Examples (in the form, [Y:a b...] for sum Y and terms a,b,...) include [3: 3], [4: 2 2], [5: 3 2], [6:3 3], [7: 3 2 2], [8: 3 3 2], [9:3 3 3], [10: 3 3 2 2] and so forth.

Upvotes: 1

georg
georg

Reputation: 214969

Let n be the number of items, and s the sum. Populate the list of size n with s // n and add 1 to the last s % n elements. This gives you the list with the max product.

max_list = [s//n] * (n - s%n) + [s//n + 1] * (s%n)

Upvotes: 2

Ankur Ankan
Ankur Ankan

Reputation: 3066

The maximum of multiplications will be when all the values are nearest to equal values.

X = [Y // 3 for i in range(3)]
difference = Y - X[0] * 3
if difference == 2:
    x[0] += 1
    X[1] += 1
elif difference == 1:
    X[0] += 1
print (X)

Output:
Y = 8
X = [3, 3, 2]
Y = 9
X = [3,3,3]
Y = 10
X = [4,3,3]

Upvotes: 0

Related Questions