Approximate factors in an average calculation

Question

here is what I want to do: I have an double[] of size N (N will not be larger than 500 but different applications of this program will have different Ns). I now want to find out what combinations I can achieve a given average with. For example:

The number I look for is 3. The double array has only 2 items in it {6,2}

the program should loop through and tell me that 1x[0] and 3x[1] = 6+2+2+2 / 4 = 3 is the easiest way to get to this. I also want to limit these factors to a maximum of say 10,000 (i.e. it can be a maximum of 10,000[0]+10,000[1])

I was experimenting with nested while loops but couldn't get it to work. A jumpstart please?

thanks

edit: here is what I have so far. it is working for the two given combinations but would be prohibitively convoluted to implement due to it requiring one for loop for each factor.

public class Test {
public static void main(String[] args) {
    double[] returns = {6,2};
    double givenReturn = 3;
    double maxStock = 5000;
    double calcReturn = 0;


    for (int a = 0; a < maxStock && (givenReturn != calcReturn); a++) {//first level

        for (int b = 0; b < maxStock && (givenReturn != calcReturn); b++) {//second level

            calcReturn = (a*returns[0]+b*returns[1])/(a+b);
            if(calcReturn == givenReturn){
                System.out.println(a+" "+b);
                break;
            }
        }

    }



}

}

the program successfully prints: "1 3".

How can I make the program work with say an array of ten different returns?

Answer 1

For reference sake, your problem put mathematically:

Given an integer T and a vector c (|c| <= 500), solve for vector a and integer b:
(all numbers are non-negative integers)
a0.c0 + a1.c1 + a2.c2 + ... = T.b
a0 + a1 + a2 + ... = b
each ai <= 10000
b > 0
Additional constraint: minimize b

For your example:

c is {6,2}, T is 3, a comes to {1, 3} and b comes to 4.

It feels like there should be a mathematical way to solve it (though I doubt there is).

Brute force will be way too slow. For 500 types up to 10000 occurrences each, we're talking about 500^10000, which is ... a lot.

I'm thinking CSP or hill climbing.

Hill climbing is easy enough to implement - you will basically just start with some random selection of elements, then add and remove elements to get closer to the target.

The wiki page on integer programming has a bit of useful information.