\section{集合分割問題}

\subsection{問題}

ある集合
\begin{equation}
	X = \{ x_1, x_2, \dots, x_n \},
\end{equation}
を
\begin{equation}
	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\},
\end{equation}
と分割することを考える．
関数
\begin{equation}
	f: X \longrightarrow \mathbb{R}, \quad g: X \longrightarrow \mathbb{R},
\end{equation}
により定義される目的関数
\begin{equation}
	c(U, V) = \sum_{u \in U} f(u) + \sum_{v \in V} g(u), \label{eq:general-cost-function}
\end{equation}
を最小化するような $U$, $V$ はどのような分割か．

\subsection{解法}

式~\eqref{eq:general-cost-function} を
\begin{align}
	c(U, V) = \sum_{u \in U} (f(u) - g(u)) + \sum_{x \in U \cup V} g(u), \label{eq:transformed-general-cost-function}
\end{align}
と変形する．
式~\eqref{eq:transformed-general-cost-function} の第2項が $U$, $V$ に対して定数であることに注意すると，式~\eqref{eq:general-cost-function} を最小化する問題は
\begin{equation}
	c'(U, V) = \sum_{u \in U} (f(u) - g(u)), \label{eq:simplified-general-cost-function}
\end{equation}
を最小化する問題に等しい．
したがって，式~\eqref{eq:simplified-general-cost-function} を最小化する $U$, $V$ は，$X$ を
\begin{equation}
	d(x) = f(x) - g(x),
\end{equation}
の昇順に並べ，最初の $\left\lfloor \frac{n}{2} \right\rfloor$ 個の要素を $U$，残りの $\left\lceil \frac{n}{2} \right\rceil$ 個の要素を $V$ とすることで求められる．