Math programming problem

Question

I have an optimization problem as follows.

Given an array of positive integers, for example. (y1 = 2, y2 = 3, y3 = 1, y4 = 4, y5 = 3) , I try to maximize the sum of the values ​​of the functions f(x) , where f(x) = x if x + y <= m and f(x) = 0 otherwise. ( m is a positive integer)

For example, in this specific example above (with m = 5 ), the optimal value of x is 2 , since the sum will be 2 + 2 + 2 + 0 + 2 = 8 , which is the highest among other possible values ​​for x (implicitly, possible x will vary between 0 and 5 )

Of course, I can exhaustively work out and compare the sums received by all possible values ​​of x, and choose x, which gives the highest amount, provided that the range x is sufficiently small. However, if the range becomes large, this method can become overly expensive.

I wonder if there is anything that I can use from things like linear programming to solve this problem more generally and correctly.

Answer 1

There is no need for linear programming, just sorting and one pass to determine the optimal x.

Pseudocode:

 getBestX(m, Y) { Y = sort(Y); bestSum = 0; bestX = 0; for (i from 0 to length(Y)) { x = m - Y[i]; currSum = x * (i + 1); if (currSum > bestSum) { bestSum = currSum; bestX = x; } } return bestX; } 

Note for each i we know that if x = m - Y[i] , then f(x) = x for each element up to and including i and f(x) = 0 for each element subsequently, since Y is in order ascending.