4

我有一个优化问题如下。

给定一个正整数数组，例如(y1 = 2, y2 = 3, y3 = 1, y4 = 4, y5 = 3)，我的目标是最大化 functions 的值的总和f(x)， wheref(x) = x if x + y <= m和f(x) = 0else 。（m是一个正整数）

例如，在上面的这个特定示例中（使用m = 5），最佳x值是2，因为总和是2 + 2 + 2 + 0 + 2 = 8，它是其他可能值中最高的x（隐式地，可能x范围为0和5）

我当然可以详尽地计算并比较所有可能的 x 值产生的总和，并选择给出最高总和的 x，前提是 x 的范围相当小。然而，如果范围变大，这种方法可能变得过于昂贵。

我想知道我是否可以从线性规划之类的东西中使用任何东西来更普遍、更正确地解决这个问题。

4

1 回答 1

3

这里不需要线性规划，只需要一次排序和一次通过即可确定最优 x。

伪代码是：

getBestX(m, Y) {
    Y = sort(Y);
    bestSum = 0;
    bestX = 0;

    for (i from 0 to length(Y)) {
        x = m - Y[i];
        currSum = x * (i + 1);
        if (currSum > bestSum) {
            bestSum = currSum;
            bestX = x;
        }
    }

    return bestX;
}

请注意，对于每个i我们都知道 if x = m - Y[i]thenf(x) = x对于直到并包括的每个元素i，以及f(x) = 0之后的每个元素，因为 Y 是按升序排列的。

于 2011-05-10T01:14:19.217 回答