algorithm - 分配给定资源(例如预算)以获得最佳输出的最佳方式

Question

我正在尝试找到一种解决方案，在该解决方案中，将给定资源(例如预算)最好地分配给不同的选项，从而根据所提供的资源产生不同的结果。

假设我有 N = 1200 和一些函数。 (a、b、c、d为一些未知变量)

f1(x) = a * x
f2(x) = b * x^c
f3(x) = a*x + b*x^2 + c*x^3
f4(x) = d^x
f5(x) = log x^d
...

此外，假设有 n 个函数根据其输入 x 产生不同的结果，其中 x = 0 或 x >= m ，其中 m 是一个常量。

虽然我无法找到给定函数的确切公式，但我能够找到输出。这意味着我可以:

X = f1(N1) + f2(N2) + f3(N3) + ... + fn(Nn) 其中 (N1 + ... Nn) = N 将 N 分配到 n 个数中的次数，并找到 X 最大的特定情况。

我将如何使用当前可用的任何库以最少的计算能力找到 N 的最佳分布？

Answer 1

如果您对限制为整数的分配感到满意，那么有一个成本为 O(Nn) 的动态规划解决方案 - 因此您可以根据需要通过缩放来提高准确性，但这会增加 cpu 时间。

对于每个 i=1 到 n 维护一个数组，其中元素 j 仅使用前 i 个函数给出最大 yield ，给它们一个总余量 j。

对于 i=1，这只是 f1() 的结果。

对于 i=k+1，在计算 j 的结果时，请考虑在 f_{k+1}() 和告诉您从前 k 个分布中获得最佳返回的表格之间拆分 j 个单位的每种可能方式函数 - 因此您可以使用为 k 创建的表计算 i=k+1 的表。

最后，您将获得 n 个功能和 N 个资源的最佳返回。如果您维护一组数组，告诉您在前 i 个函数中分配 k 个单元的最佳方式，对于 i 和 k 的所有可能值，则可以更容易地找到最佳答案。然后你可以查找 f100() 的最佳分配，从 N 中减去分配给 f100() 的值，在给定结果资源的情况下查找 f99() 的最佳分配，并继续这样直到你计算出所有 f() 的最佳分配。

例如假设 f1(x) = 2x, f2(x) = x^2 和 f3(x) = 3 如果 x>0 否则为 0。假设我们有 3 个单位的资源。

第一个表只是 f1(x)，即 0、2、4、6 表示 0、1、2、3 个单位。

第二个表是你可以使用 f1(x) 和 f2(x) 为 0、1、2、3 个单位做的最好的，是 0、2、4、9，在 x=2 时从 f1 切换到 f2 .

第三个表是 0、3、5、9。我可以通过对 f3() 使用 1 个单位得到 3 和 5，其余的用于第二个表中的最佳解决方案。 9 只是第二个表中的最佳解决方案 - 没有更好的解决方案使用 3 个资源将其中任何一个提供给 f(3)

所以 9 是这里的最佳答案。解决如何到达那里的一种方法是保留表格并重新计算该答案。 9 来自第二个表中的 f3(0) + 9，因此所有 3 个单位都可用于 f2() + f1()。第二个表 9 来自 f2(3)，因此 f(1) 没有剩余单位，我们得到 f1(0) + f2(3) + f3(0)。

当您处理要在第 i=k+1 阶段使用的资源时，您有一个表格 i=k，它准确地告诉您在您决定在第我=k+1。最佳分配不会变得不正确，因为在那个阶段 i=k 你已经计算出了给定所有可能数量的剩余资源的最佳分配的结果。