動的計画法(ナップサック問題) - アルゴリズム講習会
動的計画法の非常に丁寧なサイトを見つけたので、これを機に心の隅にずっと引っかかっていたpaizaのナップサック問題をメモ化と漸化式で解いてみた。あとで読みやすくまとめてみたい。
天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」|paizaオンラインハッカソンLite
問題や入出力形式等のREADMEはこの辺に置いた。
csny/estimate-man-month · GitHub
深さ優先探索
まずは、メモ化と漸化式を見据えての「普通の深さ優先探索」。これをベースにメモ化→漸化式というのが、作りやすい。コツは、
- returnで必ず最適解を返す作りになっていること
- そのために、一意の引き数に対して一意の結果が返る作りであること
- どこで、何を条件に再帰を止めて折り返すかというところ
あたり。コードを見てもらうとわかるが、再帰呼び出しをしているのはほんの一部だけなのです。
メモ化と漸化式で高速化はできるものの、その過程であるどことどこの会社を使ったかとか、人数は何人使ったかといったパラメータが可視化しづらいって問題はある。本当にポンっと答えだけ出す作りなんだよね。
int rec(int i, int j) { int res; const int infinite = 999999; if (j <= 0) { // 人数が条件MAN_NEEDを超えたら費用を0に、再起呼び出しはここで終了、折り返して計算。 // ここを起点に投入した会社に応じて足し算 res = 0; } else if (i == TOTALNUMBER_COMPANY) { // 会社がもう残っていない(且つj>0)ときは、最大値を入力、再起呼び出しはここで終了。 // ここを起点に投入した会社に応じて足し算 res = infinite; } else { // 会社iを入れるか入れないか選べるので、両方試して予算の和が小さい方を選ぶ // 前述の2つの条件のどちらかを満たすまで、再帰呼び出しを繰り返す /* res = min( rec(i + 1, j), rec(i + 1, j - w[i]) + v[i] ); */ if (rec(i + 1, j)<rec(i + 1, j - q[i]) + r[i]){ res = rec(i + 1, j); } else { res = rec(i + 1, j - q[i]) + r[i]; } } return res; }
estimate-man-month/main.m at master · csny/estimate-man-month · GitHub
メモ化再帰
次にメモ化再帰。今回はjがマイナスになってしまうので、そうすると配列の要素が循環して要素の一番大きいところから使ってしまうのに気付かずに、時間を使ってしまった。
dp[i][0]=dp[i][0]
dp[i][-1]=dp[i][200200]
というね。コードは単純で、先に作った深さ優先探索にメモ用の配列を用意して結果を再利用するように追記しただけ。これだけで、かなり処理が早くなる。メモ化すごい。
int rec(int i, int j) { if (dp[i][j] != -1000) { // すでに調べたことがあるならその結果を再利用 return dp[i][j]; } int res; const int infinite = 999999; if (j <= 0) { // 人数が条件MAN_NEEDを超えたら費用を0に、再起呼び出しはここで終了、折り返して計算。 // ここを起点に投入した会社に応じて足し算 // jがマイナスになる分は、循環する感じで要素数の一番大きい数字から使用される res = 0; //NSLog(@"j=%d",j); } else if (i == TOTALNUMBER_COMPANY) { // 会社がもう残っていない(且つj>0)ときは、最大値を入力、再起呼び出しはここで終了。 // ここを起点に投入した会社に応じて足し算 res = infinite; } else { // 会社iを入れるか入れないか選べるので、両方試して予算の和が小さい方を選ぶ // 前述の2つの条件のどちらかを満たすまで、再帰呼び出しを繰り返す /* res = min( rec(i + 1, j), rec(i + 1, j - w[i]) + v[i] ); */ if (rec(i + 1, j)<rec(i + 1, j - q[i]) + r[i]){ res = rec(i + 1, j); } else { res = rec(i + 1, j - q[i]) + r[i]; } } return dp[i][j] = res; }
estimate-man-month/main.m at master · csny/estimate-man-month · GitHub
漸化式
最後に漸化式。メモ化を元に場合分けしつつforループを作ればOK。今回の漸化式はこんなイメージ。注意点としては、定数を先に配列に入れてやること。
dp[i][j]
dp[会社数][j] = 999999 (0 < j <=必要人数)
dp[i][j] = 0 (0 <= i <会社数) (-200 < j <= 0)
dp[i][j] = max{dp[i+1][j], dp[i+1][j−w[i]]+v[i]} (0 <= i <会社数) (0 < j <=必要人数)
漸化式通りにdp[i][j]に値をブッ込んだら、↓としてやれば最適解が出力されるって訳。
NSLog(@"%d",dp[0][必要人数])
estimate-man-month/main.m at master · csny/estimate-man-month · GitHub
参考)
問題は違いますが、Objective-Cで幅優先探索もやってます。
コイン両替問題を3種類の探索方法で解いてみた - せでぃのブログ