Программно получить наивысшую формулу результата с 3 переменными и заданным условием

Question

У меня есть формула, которая содержит 3 переменные.Давайте назовем их x1, x2 и x3.Пользователь может ввести число, которое является суммой этих переменных и хранится в z, поэтому z=10 равно x1 + x2 +x3 =10 и z=20 равно x1+x2+x3 = 20.

Формула будет иметь следующий результат:2000 или 4591 и т. Д. Теперь я хотел бы найти x1, x2, x3 для z, чтобы он имел самый высокий результат.x1= 2 x2=3 x3=5 может дать 2500, но x1=3 x2=6 x3=1 может дать 2983 и т. Д. Для z =10

Так что если z =10, я могу попробовать цикл for и начать с X1 =0, X2=0, X3=10, а затем переберите все ситуации и сохраните результаты, но мне это кажется неэффективным.Я хотел бы найти направление для того, как я могу решить эту проблему эффективно для различных значений z и вернуть что-то вроде:

Для z = 10 наибольшее значение достигается x1=4 x2=3 x3=4 с результатом 3465.

Что касается языка программирования, я могу использовать PHP, JS, Java, C ++, Haskell.Так что дело не в языке, а в том, как решить эту проблему в целом.

Answer 1

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

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

Вот псевдокод

max = MININT     # smallest possible integer
for x1 in interval[0, 10]
    for x2 in interval[0, 10-x1]
        x3 = 10 - (x1+x2)
        value = f(x1, x2, x3)
        if value > max
            max = value
            coeff = [x1, x2, x3]

print "max value achieved at", coeff, "with a value of", max

Это тебя заводит?

Answer 2

Если я правильно понимаю ваш вопрос, похоже, вы описываете Задачу назначения

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

В вашем случае «агентами» являются 3 введенных значения, а «задачами» являются переменные x1, x2 и x3. Ваша функция стоимости была бы просто формулой (но измененной так, чтобы большие числа возвращали меньшую стоимость - возможно, что-то вроде 1-formula)

Для решения этой проблемы вам потребуется использовать Венгерский алгоритм . Я не буду вдаваться в подробности этого (но это объяснение от GeeksForGeeks объясняет это довольно хорошо). По сути, вам необходимо заполнить матрицу затрат NxN, а затем выполнить некоторые операции с этой матрицей, чтобы найти оптимальное решение. Венгерский алгоритм - это O (n ^ 3), что гораздо эффективнее, чем грубое принуждение (ошеломляющее O (n!))