How to develop algorithm for this case (other than brute force)?

Question

Suppose I have K arrays of different sizes:

A1 = [X1, X2, X3 .... Xn]

A2 = [Y1, Y2, Y3 .... Ym] .. and K-2 more such arrays.

All arrays contain elements of same data type.

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

Important Info

Nature of function: 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:

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

Xn + Ym + ... and others <= Constant

EDIT: As @Spektre asked, the function is exponential in nature.

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

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

EDIT: An example function and dataset for the above problem:

Maximize: F = a^x + b^y + c^z

The above function was not very accurate representation of original problem.

UPDATE: Example function updated

F = xh(x)^g(x) + yh(y)^g(y) + zh(z)^g(z)

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).

Example dataset (x,y,z are in millions):

x is in [20,18,17,15,12,9,8,5]

y is in [26,21,16,13,6,3,2,1]

z is in [45,42,41,40,12,3,2,1,0]

So the arrays contain random but sorted values.

And a,b,c > 1 So take a = 2, b=3 and c=4 for instance making the function as:

F = 2^x + 3^y + 4^z

The constraint: x + y + z <= 50

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.

Example code of h(), g() and arrays (in JavaScript)

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 <= 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];

Answer 1

The example data you provided so far offers some opportunities for optimization:

First of all, rather than comparing x's, y's, and z's, use the intermediate calculation, x*h(x)^g(x), or a pre-calculated table-lookup of those values. Looking at rounded and proportionally reduced output for an easier visual, x / 100000 and Math.round(x * Math.pow(h(x), g(x)) / 100000), we see that some values are more than an order of magnitude greater than others.

xs = { 20, 18, 17, 15, 12,  9,  8, 5}
     {124, 80, 65, 43, 24, 13, 11, 6}

ys = { 26,  21, 16, 13, 6, 3, 2, 1}
     {525, 155, 52, 29, 7, 3, 2, 1}

zs = {    45,    42,    41,    40, 12, 3, 2, 1}
     {192306, 66268, 46965, 33467, 24, 3, 2, 1}

Group variables and their intermediate functional results as tuples according to a calibrated choice of ranges of magnitude k. For example, using our reduced overview, let's say k = 500:

[385 * k]    [133 * k]   ...  [2 * k]
(45,192306)  (42,66268)  ...  any x or y

It makes no sense to try different possibilities for zs when we have one value that's more than 150 times greater than any x or y. Once we've removed the larger variable, our search is now: maximize f'(x,y), where x + y <= 50 - 45).

If you foresee data results with extreme differences in magnitude, because f is actually linear in the intermediate calculation, call it i(x), you could implement a calibration at each round of elimination, until faced with choices within the same order of magnitude, where you would use brute-force with a greedy early exit.

Answer 2

Well now it is much more clearer. As the max sum is applied to input variables not the output values of f then it is much more simple. So here first simple approach in C++:

double MaxSum = 50.0;
double X[] = { 20.0,18.0,17.0,15.0,12.0,9.0,8.0,5.0 };     int Nx=sizeof(X)/sizeof(double);
double Y[] = { 26.0,21.0,16.0,13.0, 6.0,3.0,2.0,1.0 };     int Ny=sizeof(Y)/sizeof(double);
double Z[] = { 45.0,42.0,41.0,40.0,12.0,3.0,2.0,1.0,0.0 }; int Nz=sizeof(Z)/sizeof(double);
double f(double x,double y,double z)
    {
    return pow(2.0,x)+pow(3.0,y)+pow(4.0,z);
    }
void solve()
    {
    int cnt;    // just tested solutions counter
    int x,y,z;
    bool init;
    double sum,a,aa,xx,yy,zz,x1,y1,z1;
    // near max sum only
    cnt=0.0;
    init=true; sum=0.0;
    for (x=0;x<Nx;x++) { x1=X[x]; sum+=x1; if (sum<=MaxSum)
    for (y=0;y<Ny;y++) { y1=Y[y]; sum+=y1; if (sum<=MaxSum)
    for (z=0;z<Nz;z++) { z1=Z[z]; sum+=z1; if (sum<=MaxSum)
        {
        cnt++;                                          // update counter for debug purposes
        a=f(X[x],Y[y],Z[z]);                            // compute actual solution
        if ((init)||(aa<a)) { init=false; aa=a; xx=x1; yy=y1; zz=z1; }  // remeber the best one
        }
    if (sum          <=MaxSum) z=Nz; sum-=z1; }
    if (sum+Z[0]     <=MaxSum) y=Ny; sum-=y1; }
    if (sum+Z[0]+Y[0]<=MaxSum) x=Nx; sum-=x1; }
    // here:
    // cnt is number of tested solutions
    // Nx*Ny*Nz is number of all possibilities
    // found solution aa=f(xx,yy,zz)
    }

Output:

[   0.027 ms]Solution 19342813113834066800000000=f(5,3,42) tested 64 of 576 combinations

The idea is test only those combinations which sum is near MaxSum constraint. As you can see the loops are almost identical so you can nest as many of them as you want. If you got variable count of the input arrays then you can use

• runtime variable depth nested for loops

Algorithm:

1. The program basically loops through "all possiblities" from the biggest one to lowest.

2. Then test only if the target sum is smaller or equal to MaxSum.

3. after that if partial sum is small enough that even if used the biggest values from unused arrays still fits into the MaxSum stop that loop to avoid un-necessary iterations. This effectively cut down the complexity from brute-force O(n^k) to O(g(n)^k) where n is average array size, k is the number of arrays and g(n) is average number of tested values per array (depends on the MaxSum,n,k and array values. In your test case g(n)=2)

Improvements:

Now if you got background information about the function f and know that some variables are more significant then others (in your test case the Z array) Then you can limit that variable on first few biggest values that still fits into that limit ignoring the small values of that array. This can be done recursively on other arrays too but VERY CAREFULLY so you do not miss the actual solution.

Answer 3

You may be interested in greedy algorithms. That's simple but useful idea. First my thought when I see such problem is try to approach using this technique.

Another approach is method of gradient descent.

Answer 4

Dynamic programming is a technique that will work well in your case. Since you know a bit more about your data -- namely that the lists are sorted -- you can optimize the search to not go too far down a sub-optimal path.

This is not a quick answer with pseudocode. I highly recommend watching MIT's algorithms course in its entirety, but Lectures 19-22 relate to dynamic programming. Here is the playlist on youtube.