Python入門トップページ


目次

  1. 「ゴチ」バトルの問題
  2. ナップサック問題と両替問題
  3. 準備
  4. Python で問題を解く
  5. ファイルを読み込んで問題を解く
  6. 遺伝的アルゴリズムを実装する
  7. 参考資料

「ゴチ」バトル

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

ハイキングに出かける際,色々なものがある中からどの荷物を持っていけば快適にハイキングができるかを考える.このとき,詰め込む荷物のサイズがナップサックの容量内で収まるように,さらに荷物から得られる満足度(利益)が最大になるように詰め込む荷物の組み合わせを考える問題がナップサック問題である.ナップサック問題は荷物に\(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\) になる料理の組み合わせを見つけるというものである.(実際には,さらに注文する料理の数を最大にしている.)

目次に戻る