Приближенные факторы в среднем расчете

Question

Вот что я хочу сделать: у меня есть double[] размера N (N будет не больше 500, но разные приложения этой программы будут иметь разные N). Теперь я хочу выяснить, с какими комбинациями я могу достичь заданного среднего. Например:

Число, которое я ищу, равно 3. В двойном массиве всего 2 элемента {6,2}

программа должна пройти цикл и сказать мне, что 1x[0] и 3x[1] = 6+2+2+2 / 4 = 3 - самый простой способ добраться до этого. Я также хочу ограничить эти факторы максимум, скажем, до 10000 (т.е. это может быть максимум 10000[0]+10000[1])

Я экспериментировал с вложенными циклами while, но не смог заставить его работать. Jumpstart, пожалуйста?

Спасибо

редактировать: вот то, что я до сих пор. он работает для двух заданных комбинаций, но будет непросто реализован из-за того, что для каждого фактора требуется один цикл for.

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;
            }
        }

    }



}

}

Программа успешно печатает: "1 3".

Как я могу заставить программу работать, скажем, с массивом из десяти разных возвратов?

Answer 1

Для справки, ваша задача математически:

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

Для вашего примера:

c это {6,2}, T это 3, a приходит к {1, 3} и b доходит до 4.

Такое ощущение, что должен быть математический способ ее решения (хотя я сомневаюсь, что он есть).

Грубая сила будет слишком медленной. Для 500 типов до 10000 экземпляров в каждом мы говорим о 500^10000, что... много.

Я думаю CSP или восхождение на холм.

Восхождение на холм достаточно легко осуществить - вы просто начнете с некоторого случайного выбора элементов, затем добавите и удалите элементы, чтобы приблизиться к цели.

На вики-странице по целочисленному программированию есть немного полезной информации.