arrays - 如何为这种情况开发算法(除了蛮力)？

Question

假设我有 K 个不同大小的数组:

A1 = [X1, X2, X3 .... Xn]

A2 = [Y1, Y2, Y3 .... Ym] .. and K-2 more such arrays.

所有数组都包含相同数据类型的元素。

然后我有一个函数，F = f(Xn, Ym,...K-2 more such elements) .该函数基本上需要每个数组中恰好一个元素，我的目标是找到该函数的最大值。而且，所有元素都使它 最大限度。

重要信息

函数的性质:所有数组都是排序的(降序)。每个数组中的第一个元素提供函数的最佳解决方案(最大化其对等集中的函数)。因此，理想情况是从每个数组中选取第一个元素。但是有一个约束条件，我最好将其描述为:

假设这些元素是数字，那么我必须使它们的总和小于某个常数值。所以约束是:

Xn + Ym + ... and others <= Constant

编辑:正如@Spektre 所问，该函数本质上是指数函数。

我怎样才能不用蛮力解决这个问题？任何关于解决类似现有问题的建议也会有所帮助!

我理解分而治之、动态规划和线性规划，达到算法导论-CLRS中所讲授的程度。因此，即使我可以应用其中任何一个，我也无法解决这个问题。

编辑:上述问题的示例函数和数据集:

最大化:F = a^x + b^y + c^z

上述函数不是原始问题的非常准确的表示。

更新:示例函数已更新

F = xh(x)^g(x) + yh(y)^g(y) + zh(z)^{g(z )}

h 和 g 是 x/y/z 的非递减线性函数。 h 的范围从 1 到 2 不等。g 的范围从 1 到 50 不等。x、y、z 的域是正实数，平均值以百万为单位(对于前面的示例，将 1000 万视为最大值)。

示例数据集(x、y、z 以百万为单位):

x is in [20,18,17,15,12,9,8,5]

y is in [26,21,16,13,6,3,2,1]

z is in [45,42,41,40,12,3,2,1,0]

所以数组包含随机但排序的值。

和a,b,c > 1因此，以 a = 2、b=3 和 c=4 为例，将函数设为:

F = 2^x + 3^y + 4^z

约束条件:x + y + z <= 50

我在 Spektre 的解决方案之后更新了示例函数，但该算法应该仍然有效，因为函数仍然是 x、y、z 的递增函数。

h()、g() 和数组(在 JavaScript 中)的示例代码

function h(a) {
    var h = 1 + 0.0000001 * a;
    return h;
}

function g(a) {
    var g = (50 / 10000000) * a;
    return g;
}

function f(x, y, z) {
    var f = x * Math.pow(h(x), g(x)) + y * Math.pow(h(y), g(y)) + z * Math.pow(h(z), g(z));
    return f;
}

var maxSum = 5000000;

function isSumLessThanMax(x, y, z) {

    if (x + y + z <= maxSum) {
        return true;
    }
    else {
        return false;
    }
}

var x = [2000000, 1800000, 1700000, 1500000, 1200000, 900000, 800000, 500000];

var y = [2600000, 2100000, 1600000, 1300000, 600000, 300000, 200000, 100000];

var z = [4500000, 4200000, 4100000, 4000000, 1200000, 300000, 200000, 100000, 0];

Answer 1

您目前提供的示例数据提供了一些优化机会:

首先，而不是比较x的，y的，和 z的，使用中间计算，x*h(x)^g(x) ，或这些值的预先计算的表查找。查看圆形和按比例缩小的输出以获得更轻松的视觉效果，x / 100000和 Math.round(x * Math.pow(h(x), g(x)) / 100000) ，我们看到一些值比其他值大一个数量级以上。

xs = { 20, 18, 17, 15, 12,  9,  8, 5}
     {124, 80, 65, 43, 24, 13, 11, 6}

ys = { 26,  21, 16, 13, 6, 3, 2, 1}
     {525, 155, 52, 29, 7, 3, 2, 1}

zs = {    45,    42,    41,    40, 12, 3, 2, 1}
     {192306, 66268, 46965, 33467, 24, 3, 2, 1}

根据经过校准的量级范围选择，将变量及其中间函数结果分组为元组 k .例如，使用我们简化的概览，假设 k = 500 :

[385 * k]    [133 * k]   ...  [2 * k]
(45,192306)  (42,66268)  ...  any x or y

为 zs 尝试不同的可能性是没有意义的当我们有一个值比任何 x 大 150 倍以上时或 y .一旦我们删除了较大的变量，我们现在的搜索是:maximize f'(x,y), where x + y <= 50 - 45) .

如果您预见数据结果在幅度上存在极端差异，因为 f在中间计算中实际上是线性的，称之为i(x) ，您可以在每一轮淘汰赛中实现校准，直到面临相同数量级的选择，您将使用蛮力和贪婪的提前退出。