「ゴチ」バトル

ナップサック問題と両替問題

ハイキングに出かける際，色々なものがある中からどの荷物を持っていけば快適にハイキングができるかを考えます．このとき，詰め込む荷物のサイズがナップサックの容量内で収まるように，さらに荷物から得られる満足度（利益）が最大になるように詰め込む荷物の組み合わせを考える問題がナップサック問題です．ナップサック問題は荷物に$1$ から $n$ の番号をつけ，変数 $x_j~(j=1,\cdots,n)$ を導入することによって数学的に定式化することができます．変数 $x_j$ の意味は次のとおりです．

\begin{equation} x_j = \left\{ \begin{array}{ll} 1 & \mbox{荷物 $j$ を選択する} \\ 0 & \mbox{荷物 $j$ を選択しない} \end{array} \right. \end{equation}

荷物 $j$ の重さを $w_j$，利益を $p_j$，ナップサックの容量を $c$ とすると，基本的なナップサック問題（0-1ナップサック問題と呼ばれる）は次のように定式化することができます．

\begin{equation} \begin{array}{lll} \mbox{maximize} & \displaystyle \sum_{j=1}^{n}p_jx_j & \\ \mbox{subject to} & \displaystyle \sum_{j=1}^{n}w_jx_j \leq c, & \\ & x_j = 0 \mbox{ or } 1, & j=1,\cdots,n. \\ \end{array} \end{equation}

「ゴチ」バトルの問題は制約付き両替問題として考えることができます．制約付き両替問題はナップサック問題の特殊なケースです．実用的な例として，スーパーやコンビニのレジでの精算において，釣り銭を返す際にレジにあるできるだけ多種の紙幣，硬貨を使用するにはどのような組み合わせを選択すればよいかという問題である（あるいは種類を最小にする問題もできる）．この問題は次のように定式化されます．

\begin{equation} \begin{array}{lll} \mbox{maximize} & \displaystyle \sum_{j=1}^{n}x_j & \\ \mbox{subject to} & \displaystyle \sum_{j=1}^{n}w_jx_j = c, & \\ & 0 \leq x_j \leq b_j, & j=1,\cdots,n, \\ & x_j \mbox{ integer}, & j=1,\cdots,n. \\ \end{array} \end{equation}

上記の制約付き両替問題において $b_j = 1$ としたとき（つまり，それぞれの紙幣，硬貨は1つずつしかないとき，「ゴチ」バトルの例では1つの料理は1皿しか注文できないとき），次のようになります．

\begin{equation} \begin{array}{lll} \mbox{maximize} & \displaystyle \sum_{j=1}^{n}x_j & \\ \mbox{subject to} & \displaystyle \sum_{j=1}^{n}w_jx_j = c, & \\ & x_j = 0 \mbox{ or } 1, & j=1,\cdots,n. \\ \end{array} \end{equation}

これは「ゴチ」バトルの定式化そのものです．つまり，与えられたメニューの中から価格の合計がちょうど $c$ になる料理の組み合わせを見つけるというものです．（実際には，さらに注文する料理の数を最大にしています．）

目次に戻る

« 戻る次へ »