問題

ある集合 $X = { x_1, x_2, \dots, x_n }$ を次のように分割することを考える:

\[U = \left\{ x_1, x_2, \dots, x_{\left\lfloor \frac{n}{2} \right\rfloor} \right\}, \quad V = \left\{ x_{\left\lfloor \frac{n}{2} \right\rfloor + 1}, x_{\left\lfloor \frac{n}{2} \right\rfloor + 2}, \dots, x_n \right\}.\]

関数 \(f: X \to \mathbb{R}\), \(g: X \to \mathbb{R}\) により定義される次の目的関数

\[c(U, V) = \sum_{u \in U} f(u) + \sum_{v \in V} g(u), \tag{1}\]

を最小化するような \(U\), \(V\) を構成せよ.

解法

\(\eqref{\tag{1}}\) の \(c(U, V)\) を次のように変形する:

\[c(U, V) = \sum_{u \in U} (f(u) - g(u)) + \sum_{x \in U \cup V} g(u).\]

右辺の第 2 項が定数であることに注意すると,\(c(U, V)\) を最小化することは次の \(c'(U, V)\) を最小化することと等しい:

\[c'(U, V) = \sum_{u \in U} (f(u) - g(u)).\]

\(c'(U, V)\) を最小化する \(U\), \(V\) は,すべての \(x \in X\) を \(d(x) = f(x) - g(x)\) の昇順に並べ,最初の \(\left\lfloor \frac{n}{2} \right\rfloor\) 個からなる集合を \(U\),残りの \(\left\lceil \frac{n}{2} \right\rceil\) 個からなる集合を \(V\) とすることで得られる.

謝辞

@shora_kujira 氏にアドバイスいただきました.