4

次のような最適化問題があります。

たとえば、正の整数の配列が与えられた場合、(y1 = 2, y2 = 3, y3 = 1, y4 = 4, y5 = 3)関数の値の合計を最大化することを目指しています。(は正の整数)f(x)f(x) = x if x + y <= mf(x) = 0m

たとえば、上記の特定の例 ( を使用) では、合計が になるためm = 5、最適なx値はであり、これは の他の可能な値の中で最も高くなります(暗黙的に、可能な値はから までの範囲になります) 。22 + 2 + 2 + 0 + 2 = 8xx05

もちろん、x の範囲が適度に小さい場合は、考えられるすべての x 値の合計を徹底的に計算して比較し、最大の合計を与える x を選択することができます。ただし、範囲が大きくなると、この方法は非常に高価になる可能性があります。

この問題をより一般的かつ適切に解決するために、線形計画法などから使用できるものがあるのではないかと思います。

4

1 に答える 1

3

ここでは線形計画法は必要ありません。最適な x を決定するための並べ替えと 1 回のパスだけです。

擬似コードは次のとおりです。

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;
}

Y は昇順であるため、 までのすべての要素、およびその後のすべての要素について、 if theniがわかっていることに注意してください。x = m - Y[i]f(x) = xif(x) = 0

于 2011-05-10T01:14:19.217 に答える