algorithm - 以编程方式获得具有 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

如果我没有正确理解你的问题，那么你似乎在描述 Assignment Problem

The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.

在您的例子中，“代理”是 3 个输入值，“任务”是变量 x1、x2 和 x3。您的成本函数只是公式(但经过修改以便更大的数字返回更小的成本 - 可能类似于 1-formula)

要解决这个问题，您需要使用 Hungarian Algorithm .我不打算详述它的所有细节(但 GeeksForGeeks 的 this 解释解释得很好)。基本上，您需要完成一个 NxN 成本矩阵，然后对该矩阵进行一些操作以找到最优解。匈牙利算法是 O(n^3) - 这比蛮力强制它更有效(这是一个惊人的 O(n!))