動的計画法を使ってナップサック問題を解いてみた(計算編)【経営工学を専門にしている大学生の日記】


こんにちは!しゅんです!

今回の記事では動的計画法を使ってナップサック問題を解いていきたいと思います!

動的計画法は最適化問題を解くための手法の1つで、ナップサック問題は組合せ最適化問題の1つです。

今回のテーマは
・手計算で動的計画法をやる  ← 今回はここ!
・なぜ再帰式が成り立つのか説明する
・pythonで動的計画法をやる

の3部構成になっています!


それではやっていきましょう!



普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください!



このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。

このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます!


ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。


そもそも経営工学とは何なのでしょうか。Wikipediaによると

経営工学(けいえいこうがく、英: engineering management)は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。

引用元 : 経営工学 – Wikipedia

長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。


ナップサック問題ってなに?


まず最初にナップサック問題の説明をします。今自分がナップサックを持っています。しかしこのナップサックは容量制限が10kgであり、それ以上物を入れることができません。今このナップサックに物を詰めることを考えます。


物は最大でも1つしか持っていくことができません。物にはそれぞれ重量と満足度が割り当てられており、満足度の合計が最も大きくなるような物の組合せを見つける問題がナップサック問題です。



動的計画法ってなに?


動的計画法を簡単に説明すると

問題を解くときに元の問題を複数のサブ問題に分割して、それらの答えを記憶し、その答えを利用して元の問題の答えを見つける方法


という風になります。


元の問題をそのまま解くのは大変だけど、これまで解いてきたサブ問題の答えを使えば元の問題も解けるよね、そしてこれまで解いてきたサブ問題の答えを使わなかきゃいけないから答えを覚えてないといけないよね、っていうのが動的計画法のイメージです。

動的計画法はこちらの記事で詳しく説明しています!



現在制作中




動的計画法でナップサック問題解くための再帰式


今回は以下の再帰式を用いることでナップサック問題が解けます。

物が\(n\)個あり、その中の最初の\(i\)個だけから選び、重量制限が\(x\)のナップサック問題を考える。この問題の最適値を\(P(i,x)\)とすると、以下の式が成り立つ。

\(\begin{equation} P(i,x)= \begin{cases}P(i-1,x) & (a_i>x) \\ \max\{P(i-1,x),\;P(i-1,x-a_i)+c_i\} & (a_i \leq x) \end{cases} \end{equation}\)

但し\(a_i\)は物\(i\)の重量、\(c_i\)は物\(i\)の満足度


例えば最初の3個から物を選び、重量制限が5kgのサブ問題の最適値は\(P(3,5)\)となります。元の問題の重量制限を\(b\)kgとすると、元の問題の最適解は\(P(n,b)\)となります。


この記事ではあの再帰式が成り立つことを認めて話を進めていきます。式だけじゃ分かりにくいので、例えば物が2個の場合を考えてみましょう。


最終的には\(P(2,3)\)を求めたいので、それを求めるために\(i=1,2,\;j=0,1,2,3\)の場合を1つずつ考えてみます。まず最初に\(i=1\)の場合を考えてみましょう。つまり物1しか持っていけない場合を考えます。


\(P(1,0)=0\)です。なぜなら重量制限が0kgだと物1を持っていけないからです。

\(P(1,1)=0\)です。なぜなら重量制限が1kgだと物1を持っていけないからです。

\(P(1,2)=40\)です。なぜなら重量制限が2kgだと物1を持っていけるからです。

\(P(1,3)=40\)です。なぜなら重量制限が3kgだと物1を持っていけるからです。


\(i=1\)のときは簡単に求めることができました。ここからが本番です。あの再帰式を使って\(i=2\)のときも計算してみましょう。

あの再帰式(再掲)

物が\(n\)個あり、その中の最初の\(i\)個だけから選び、重量制限が\(x\)のナップサック問題を考える。この問題の最適値を\(P(i,x)\)とすると、以下の式が成り立つ。

\(\begin{equation} P(i,x)= \begin{cases}P(i-1,x) & (a_i>x) \\ \max\{P(i-1,x),\;P(i-1,x-a_i)+c_i\} & (a_i \leq x) \end{cases} \end{equation}\)

但し\(a_i\)は物\(i\)の重量、\(c_i\)は物\(i\)の満足度


\(P(2,0)=0\)です。なぜなら\(a_2=1>0=x\)なので\(P(2,0)=P(2-1,0)=P(1,0)=0\)となるからです。さっき求めた\(P(1,0)\)の値を利用しています。

\(P(2,1)=30\)です。なぜなら\(a_2=1 \leq 1 = x\)なので\(P(2,1)=\max\{P(2-1,1), \; P(2-1,1-1)+c_2\}\)
\(=\max\{P(1,1), \; P(1,0)+30\}=\max\{0,\;30\}=30\)となるからです。さっき求めた\(P(1,1)\)と\(P(1,0)\)の値を利用しています。

\(P(2,2)=40\)です。なぜなら\(a_2=1 \leq 2 = x\)なので\(P(2,2)=\max\{P(2-1,2), \; P(2-1,2-1)+c_2\}\)
\(=\max\{P(1,2), \; P(1,1)+30\}=\max\{40,\;30\}=40\)となるからです。さっき求めた\(P(1,2)\)と\(P(1,1)\)の値を利用しています。

\(P(2,3)=70\)です。なぜなら\(a_2=1 \leq 3 = x\)なので\(P(2,3)=\max\{P(2-1,3), \; P(2-1,3-1)+c_2\}\)
\(=\max\{P(1,3), \; P(1,2)+30\}=\max\{40,\;70\}=70\)となるからです。さっき求めた\(P(1,3)\)と\(P(1,2)\)の値を利用しています。


ということで\(P(2,3)\)の値を求めることができました。このように動的計画法を使えば、これまでに計算した値を使って機械的に元の問題の答えを導き出すことができます。


例題


最後に以下の問題を解いてみましょう。


下の表を埋めて満足度が最大になるような組合せを求めてみてください!


\(P(1,0)=0\)
\(P(1,1)=20\)
\(P(1,2)=20\)
\(P(1,3)=20\)
\(P(1,4)=20\)
\(P(1,5)=20\)
\(P(1,6)=20\)
\(P(1,7)=20\)
\(P(1,8)=20\)


\(P(2,0)=P(1,0)=0\;\;(a_2=3 > 0=x)\)
\(P(2,1)=P(1,1)=20\;\;(a_2=3 > 1=x)\)
\(P(2,2)=P(1,2)=20\;\;(a_2=3 > 2=x)\)
\(P(2,3)=\max\{P(1,2),\;P(1,0)+30\}=30\;\;(a_2=3 \leq 3=x)\)
\(P(2,4)=\max\{P(1,3),\;P(1,1)+30\}=50\;\;(a_2=3 \leq 4=x)\)
\(P(2,5)=\max\{P(1,4),\;P(1,2)+30\}=50\;\;(a_2=3 \leq 5=x)\)
\(P(2,6)=\max\{P(1,5),\;P(1,3)+30\}=50\;\;(a_2=3 \leq 6=x)\)
\(P(2,7)=\max\{P(1,6),\;P(1,4)+30\}=50\;\;(a_2=3 \leq 7=x)\)
\(P(2,8)=\max\{P(1,7),\;P(1,5)+30\}=50\;\;(a_2=3 \leq 8=x)\)


\(P(3,0)=P(2,0)=0\;\;(a_3=5 > 0=x)\)
\(P(3,1)=P(2,1)=20\;\;(a_3=5 > 1=x)\)
\(P(3,2)=P(2,2)=20\;\;(a_3=5 > 2=x)\)

\(P(3,3)=P(2,3)=30\;\;(a_3=5 > 3=x)\)
\(P(3,4)=P(2,4)=50\;\;(a_3=5 > 4=x)\)
\(P(3,5)=\max\{P(2,5),\;P(2,0)+70\}=70\;\;(a_3=5 \leq 5=x)\)
\(P(3,6)=\max\{P(2,6),\;P(2,1)+70\}=90\;\;(a_3=5 \leq 6=x)\)
\(P(3,7)=\max\{P(2,7),\;P(2,2)+70\}=90\;\;(a_3=5 \leq 7=x)\)
\(P(3,8)=\max\{P(2,8),\;P(2,3)+70\}=100\;\;(a_3=5 \leq 8=x)\)


\(P(4,0)=P(3,0)=0\;\;(a_4=2 > 0=x)\)
\(P(4,1)=P(3,1)=20\;\;(a_4=2 > 1=x)\)
\(P(4,2)=\max\{P(3,2),\;P(3,0)+20\}=20\;\;(a_4=2 \leq 2=x)\)
\(P(4,3)=\max\{P(3,3),\;P(3,1)+20\}=40\;\;(a_4=2 \leq 3=x)\)
\(P(4,4)=\max\{P(3,4),\;P(3,2)+20\}=50\;\;(a_4=2 \leq 4=x)\)
\(P(4,5)=\max\{P(3,5),\;P(3,3)+20\}=70\;\;(a_4=2 \leq 5=x)\)
\(P(4,6)=\max\{P(3,6),\;P(3,4)+20\}=90\;\;(a_4=2 \leq 6=x)\)
\(P(4,7)=\max\{P(3,7),\;P(3,5)+20\}=90\;\;(a_4=2 \leq 7=x)\)
\(P(4,8)=\max\{P(3,8),\;P(3,6)+20\}=110\;\;(a_4=2 \leq 8=x)\)


最適解:物1、物3、物4
最適値:110



おわりに


いかがでしたか。

今回の記事では動的計画法について解説していきました。

今後もこのような組合せ最適化に関する記事を書いていきます!

最後までこの記事を読んでくれてありがとうございました。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA