動的計画法(ナップサック問題について)
今回は、自分の大学の講義で数日前に扱われた有名な動的計画法の問題、ナップサック問題についてのプログラミングの解説をC言語でしてみようと思います。
理由は、講義の説明だとわかりづらいなと思ったからです。ただ、この解説をするのはとても難しいと思ったので、自分なりに人に説明するならどう説明するか？をまとめてみようと思いました。
はじめに
初期条件を設定します。与えられる数字はすべて自然数とし、大きさを100までとしておきます。
今回は、個の荷物が与えられ、
番目の荷物の重量を
番目の荷物の値段を
とします(ここで、は
〜
のどれかです)。
また、荷物はそれぞれ1つずつしかありません。なので、入れるか入れないかの2通りとなります。
この時に、という重さまでは入れても耐えられるカバンがあり(
より大きくすると壊れるということです)、入れた荷物の合計の値段を出来るだけ多くしましょう、という問題を解くことにします。
全探索で解いてみる
番目の荷物に対しては、入れるor入れないの2つの選択肢しかないので、全ての荷物についてその選択肢からどちらかを選びます。
これを繰り返し、以内かつ値段が最大になるようなものを探します。
これは、2通りが個存在するので、全てのパターンを網羅すると
(通り)
となります。
今回はこの方法がメインではないので、こちらのコードは省略します。
全探索すると、が増えるにつれてどんどん莫大な計算が必要になることがわかります。
動的計画法で解いてみる
では、実際に動的計画法を使ってみましょう。
簡単に言うと、最終的な最適解(最大値)を求めるために、少しスケールを小さくした問題の最適解を利用するというイメージです。
さまざまなスケールの問題の答えをメモする配列を作成します。ここでは
とします。
具体的には、番目まで(
〜
番)の荷物を使って、重量制限を
とした時の最適解をここに格納することにします。 つまり、
は
~
の範囲内にあります。
最終的な答えは、
という場所に存在します。
では、どのようにこの配列を利用するかを考えたいと思います。今回は、いくつかに場合分けをして考察していきます。
①
または
が
の時
はじめに、すぐ答えが求まるパターンについて考えます。
が
のとき、
は、
番目までの荷物を用いて、重量制限
内でできる最大の値段の合計、というものでした。
ここで、番目の荷物とはなんでしょう？
…そんなものはありません。よって、カバンに詰める荷物がそもそもないので、答えは0になります。
が
のとき、
は、
番目までの荷物を用いて、重量制限0内で値段を最大にするという問題の答えになります。
重量制限が0なので、荷物の重さは0以下の物しか入れることができません。今回はそのような荷物がないので、答えは0です。
以上より、または
が
の時、最適解はすべて0となります。式に直すと、
となります。
➁,がどちらも0でない時
いよいよ本格的に最適解を求めます。まずは、大きく２つに分類して考えます。番目の荷物を、重量制限が
のカバンに詰めることができるかどうか、です。これは
と
のように場合分けすることができます。
(ⅰ)
のとき
番目の荷物はカバンに詰めることができるでしょうか？
答えはNOです。なぜなら、番目の荷物を詰めた時点で、重量制限である
を超えてしまうため、カバンが壊れてしまうからです。では、この時の最適解、
はどうなるでしょうか。そもそもの
の定義に戻ってみます。
"〜
"番の荷物を使って、重量制限を"
"とした時の最適解
ですが、今番目の荷物はいれることができないとわかっています。よって、次のように置き換えることができます。
"〜
"番の荷物を使って、重量制限を"
"とした時の最適解
これは、dpの配列でいうとどこを表しているかというと、となります。よって、一つ目の条件式が完成しました。
のとき
(ⅱ)
のとき
のこり半分について考えます。今回は、番目の荷物をカバンに詰めることができます。
ここで、また場合分けをしましょう。番目の荷物を入れるか、入れないかの2通りで場合分けをします。 それぞれを考えた後に、より値段が高くなるようなパターンを最後に選択すればよいのです。
(A)番目を入れないとき
入れないパターンを先に考えるのには理由があります。実は、すでに答えがでています。
今、~
番目の荷物での最適解を求めようとしています。ですが、
を入れないということは、残った
~
番目の荷物で重量制限が
の時の最適解を求めることと同じになります。
見覚えがありますね。これは、の場合と全く同じ答えになります。つまり、答えの候補の1つが次のように求まります。
のときの答え候補1:
(B)番目を入れるとき
いよいよ最後です。番目の荷物を入れると、
だけカバンが重くなりますが、代わりに
の値段だけ価値が増えます。
としたときのカバンを表しています。グレーの部分が
番目の荷物を入れた部分、真っ白い部分がまだ荷物を入れることができる、空の部分です。この白い部分は、
であることがわかります。この空の部分に入れるべき荷物が何かを考えていきます。
番目の荷物は先ほど入れてしまいました。なので、手元に残っている荷物は
~
番目となります。ということは、
~
番目の荷物のなかで、先ほどの白い部分に入れる荷物の最適解を求めなければなりません。つまり、
"〜
"番の荷物を使って、重量制限を"
"とした時の最適解
を求める必要があるわけです。これは、dpという配列のどこに書いてあるかというと、
にあることがわかります。よって、カバン全体では、これに
を加えたものがi番目の荷物を入れたときの解の候補となります。したがって次のようになります。
のときの答え候補2:
A,Bの候補が出そろったので、この二つの最大値をとってあげましょう。の時の解は次のようになります。
のとき
ここで、とは、
と
のうち大きい方を取る、ということです。これはc++で使えますが、式を見やすくするためここでも使用することにします。
最終的な解を求める
①,➁から、最終的な解を求めます。といっても、まとめるだけです。
これで解が求まりました。この条件式を用いて計算をしようとすると、回計算するだけで済むようになります。最終的な答えは、for文を二重にして、
と
を
から順番に
,
まで動かしていけば求めることができます。
最後に、自分のコードをあげておきます。今回は、
としています。
また、C言語を用いています。
#include <stdio.h> #define M 10 #define N 5 //-1はダミーです。 int w[N+1]={-1,3,2,3,4,5}; int v[N+1]={-1,2,1,2,4,1}; int dp[M+1][M+1]; int main(void){ int i,j,k; for(i=0;i<=M;i++)for(j=0;j<=M;j++)dp[i][j]=0; printf("DPtable\n |w "); for(i=0;i<=M;i++)printf("%d ",i); printf("\n"); printf("-+-------------------------"); printf("\nv|\n"); for(i=0;i<=N;i++){ printf("%d| ",i); for(j=0;j<=M;j++){ int x,y=-1; if(i!=0){ x = dp[i-1][j]; if(j>=w[i])y = dp[i-1][j-w[i]]+v[i]; if(x>y)dp[i][j]=x; else dp[i][j]=y; } printf("%d ",dp[i][j]); } printf("\n"); } printf("\nanswer = %d\n",dp[N][M]); return 0; }
答えは次のようになります。
DPtable |w 0 1 2 3 4 5 6 7 8 9 10 -+------------------------- v| 0| 0 0 0 0 0 0 0 0 0 0 0 1| 0 0 0 2 2 2 2 2 2 2 2 2| 0 0 1 2 2 3 3 3 3 3 3 3| 0 0 1 2 2 3 4 4 5 5 5 4| 0 0 1 2 4 4 5 6 6 7 8 5| 0 0 1 2 4 4 5 6 6 7 8 answer = 8
このようにして、普通ならが増えると莫大な時間がかかるようなものでも、うまく条件式をつくり、小さいスケールから考えていくことで、計算の時間を減らすことができます。
ただし、今回の解き方でも、や
が整数でなかったり、
がとてつもなく大きい問題だと計算に時間がかかる場合があります。その場合では、今とは異なる条件式を組み立てる方がよいでしょう。
最後になりますが、AOJで公開されているナップサック問題を一つあげておきます。今回の考え方でとけるので、ぜひやってみてください。
