A mathematical programming problem

Question

I have an optimization problem as follows.

Given an array of positive integers, e.g. (y1 = 2, y2 = 3, y3 = 1, y4 = 4, y5 = 3), I aim to maximize the sum of the values of 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 particular example above (with m = 5), the optimal x value is 2, as the sum would be 2 + 2 + 2 + 0 + 2 = 8, which is the highest among other possible values for x (implicitly, possible x would range from 0 and 5)

I can of course exhaustively work out and compare the sums resulted by all possible x values and select the x that gives the highest sum, provided that the range of x is reasonably small. However, if the range becomes large, this method may become excessively expensive.

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

Answer 1

There is no need for linear programming here, just a sort and a single pass to determine the optimal x.

The pseudocode is:

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 every element up to and including i, and f(x) = 0 for every element afterwards, since Y is in ascending order.