How to develop algorithm for this case (other than brute force)?
<p>Suppose I have K arrays of different sizes: </p>

<pre><code>A1 = [X1, X2, X3 .... Xn]

A2 = [Y1, Y2, Y3 .... Ym] .. and K-2 more such arrays.
</code></pre>

<p>All arrays contain elements of same data type. </p>

<p>And then I have a function, <code>F = f(Xn, Ym,...K-2 more such elements)</code>. The function basically requires <em>exactly one</em> element from each array, and my objective is to find a maximum value for this function. And also, which all elements make it 
maximum. </p>

<p><strong>Important Info</strong></p>

<p><em>Nature of function:</em> All arrays are sorted (descending order). And first element in each array provides the best solution to the function (maximizes the function within its peer set). So, the ideal case would be picking up the first element from each array. But there is a constraint, which I can best describe as:</p>

<p>Suppose these elements are numbers, then I have to keep their total sum less than some constant value. So the constraint is: </p>

<pre><code>Xn + Ym + ... and others &lt;= Constant
</code></pre>

<p><strong>EDIT</strong>: As @Spektre asked, the function is exponential in nature. </p>

<p>How can I solve this without brute force? Any pointers on solutions to similar existing problems would also help! </p>

<p>I understand divide &amp; conquer, dynamic programming and linear programming upto the extent taught in <em>Introduction to Algorithms-CLRS</em>. So, if I can apply any of those, I am not able to figure that out with respect to this problem.</p>

<p><strong>EDIT</strong>: An example function and dataset for the above problem:</p>

<p>Maximize: <strike><em>F = a<sup>x</sup> + b<sup>y</sup> + c<sup>z</sup></em></strike></p>

<p>The above function was not very accurate representation of original problem. </p>

<p><strong>UPDATE: Example function updated</strong></p>

<p><em>F = xh(x)<sup>g(x)</sup> + yh(y)<sup>g(y)</sup> + zh(z)<sup>g(z)</sup></em></p>

<p>h and g are non decreasing linear function of x/y/z. Range of h varies from 1 to 2. Range of g varies from 1 to 50. Domain of x,y,z is positive real numbers with average value in millions (consider 10 million as maximum for the example case ahead).</p>

<p>Example dataset (x,y,z are in millions):</p>

<p><code>x is in [20,18,17,15,12,9,8,5]</code></p>

<p><code>y is in [26,21,16,13,6,3,2,1]</code></p>

<p><code>z is in [45,42,41,40,12,3,2,1,0]</code></p>

<p>So the arrays contain random but sorted values. </p>

<p><del>And <code>a,b,c &gt; 1</code> So take a = 2, b=3 and c=4 for instance making the function as: </del></p>

<p><del><em>F = 2<sup>x</sup> + 3<sup>y</sup> + 4<sup>z</sup></em> </del></p>

<p>The constraint: <code>x + y + z &lt;= 50</code></p>

<p><em>I've updated the example function after Spektre's solution, but that algorithm should still be valid as function is still an increasing function of x,y,z.</em></p>

<p><strong><em>Example code of h(), g() and arrays (in JavaScript)</em></strong></p>

<pre><code>function h(a) {
    var h = 1 + 0.0000001 * a;
    return h;
}

function g(a) {
    var g = (50 / 10000000) * a;
    return g;
}

function f(x, y, z) {
    var f = x * Math.pow(h(x), g(x)) + y * Math.pow(h(y), g(y)) + z * Math.pow(h(z), g(z));
    return f;
}

var maxSum = 5000000;

function isSumLessThanMax(x, y, z) {

    if (x + y + z &lt;= maxSum) {
        return true;
    }
    else {
        return false;
    }
}

var x = [2000000, 1800000, 1700000, 1500000, 1200000, 900000, 800000, 500000];

var y = [2600000, 2100000, 1600000, 1300000, 600000, 300000, 200000, 100000];

var z = [4500000, 4200000, 4100000, 4000000, 1200000, 300000, 200000, 100000, 0];
</code></pre>