読者です 読者をやめる 読者になる 読者になる

たぶん週刊「今週の進捗」

1週間に勉強したことや実装したことをネタに、週に1回(主に土日に)更新していく予定です。「多分」なので、臨時休刊があってもご海容ください。

動的計画法で解く

縦Hマス横Wマスに分割された長方形の領域Aに、
空きのマスと空きでないマスがある。
n個の長方形anに、縦Hnマス、横Wnマスの任意の大きさが与えられたとき、
各長方形を空きのマスに配置できる場所は
それぞれいくつあるかを求めるプログラムを書け。

A:       W
  □□□■□
  □□□□□
H □■□□■
  □□□□□
  □□■□□
□:空きのマス
■:空きでないマス

という問題と動的計画法を用いた模範解答のプログラムがWeb上で転がってたので、
そこからアルゴリズムを考えてみた。
飽くまで他人のプログラムを基に考えた、
「こういうアルゴリズムなんじゃないかなぁ」というもの
なので
ご容赦を。


まず上述のような領域の空き情報を配列a[H][W]に持っていたとする。

a [][0] [][1] [][2] [][3] [][4]
[0][] 空き 空き 空き    空き
[1][] 空き 空き 空き 空き 空き
[2][] 空き    空き 空き   
[3][] 空き 空き 空き 空き 空き
[4][] 空き 空き    空き 空き

動的計画法の計算に使う整数型の二次元配列dp[H][W+1]を宣言し、
整数型で表せる最大の数(めんどくさいのでここではIntMaxで表す)で初期化する。
(H,Wは領域Aの縦,横の大きさ ここではW=H=5)
dp[*][W] は0で初期化する。

dp [][0] [][1] [][2] [][3] [][4] [][5]
[0][] IntMax IntMax IntMax IntMax IntMax 0
[1][] IntMax IntMax IntMax IntMax IntMax 0
[2][] IntMax IntMax IntMax IntMax IntMax 0
[3][] IntMax IntMax IntMax IntMax IntMax 0
[4][] IntMax IntMax IntMax IntMax IntMax 0

大きさ別に何箇所配置できるかを格納する配列answer[H+1][W+1]。
0で初期化する。

ここから配置できる数を計算する過程に入ります。

まずa[0][]から順に、H1,W1〜W(=5)の小領域がいくつ配置出来るかを求めます。

  1. a[0][j]が空きでなければdp[0][i]=0、空きならば、
    1. j==0 のとき dp[0][j]==0ならばdp[0][j]=0, dp[0][j]!=0ならば1
    2. j!=0 のとき dp[0][j]=min( dp[0][j-1]+1, dp[0][j])

a[0]に対してこの処理を行うとdp[]は

dp [][0] [][1] [][2] [][3] [][4] [][5]
[0][] 1 2 3 0 1 0
[1][] IntMax IntMax IntMax IntMax IntMax 0
[2][] IntMax IntMax IntMax IntMax IntMax 0
[3][] IntMax IntMax IntMax IntMax IntMax 0
[4][] IntMax IntMax IntMax IntMax IntMax 0

こうなる。
するとdp[0][j]は、
a[0][j]の位置に置ける縦1マスの小領域の横の大きさの最大値となる。
(dp[0][2]=3は、「a[0][2]には縦1マスなら横3マスまでの小領域が置ける」という意味)

dp[1]〜dp[4]も同様に処理を行うと

dp [][0] [][1] [][2] [][3] [][4] [][5]
[0][] 1 2 3 0 1 0
[1][] 1 2 3 4 5 0
[2][] 1 0 1 2 0 0
[3][] 1 2 3 4 5 0
[4][] 1 2 0 1 2 0

ここまで終わったら、いよいよanswer[1][w]に、
縦1マス横wマスの領域がいくつ配置できるかを計算していきます。
これはdp[i][j]>=wとなっている要素を数えてanswer[1][w]に格納すればよろしい。

answer [][0] [][1] [][2] [][3] [][4] [][5]
[0][] 0 0 0 0 0 0
[1][] 0 21 13 7 4 2
[2][] 0 0 0 0 0 0
[3][] 0 0 0 0 0 0
[4][] 0 0 0 0 0 0
[5][] 0 0 0 0 0 0

さて、これで縦1マスの領域が置ける数はわかりました。
次からは縦2マス以上の領域が置ける数を求めます。

まず縦2横wの領域は、縦1横wの領域の下(a[i][j]に対してa[i+1][j])に
更に空きがあればそこに置くことが出来る。
なので、

  1. a[i+1][j]が空きでなければdp[i][j]=0、空きならば、
    1. j==0 のとき dp[i][j]==0ならばdp[i][j]=0, dp[i][j]!=0ならばdp[i][j]=1
    2. j!=0 のとき dp[i][j]=min( dp[i][i-1]+1, dp[i][j])

これをdp[0]〜dp[3]に対して処理すると(1つ下を参照するので最下段はやらない)

dp [][0] [][1] [][2] [][3] [][4] [][5]
[0][] 1 2 3 0 1 0
[1][] 1 0 1 2 0 0
[2][] 1 0 1 2 0 0
[3][] 1 2 0 1 2 0
[4][] 1 2 0 1 2 0

これでdp[i][0-3]は、
a[i][0-3]の位置に置ける縦2マスの小領域の横の大きさの最大値となる。

で、縦1マスのときと同じようにanswer[2]を更新します。
(dp[4]
はカウントの対象外)

answer [][0] [][1] [][2] [][3] [][4] [][5]
[0][] 0 0 0 0 0 0
[1][] 0 21 13 7 4 2
[2][] 0 14 6 1 0 0
[3][] 0 0 0 0 0 0
[4][] 0 0 0 0 0 0
[5][] 0 0 0 0 0 0

縦3マスの領域についても同様に処理を行うと

answer [][0] [][1] [][2] [][3] [][4] [][5]
[0][] 0 0 0 0 0 0
[1][] 0 21 13 7 4 2
[2][] 0 14 6 1 0 0
[3][] 0 7 1 0 0 0
[4][] 0 4 0 0 0 0
[5][] 0 1 0 0 0 0

ここまですれば、縦h横wの大きさをanswer[h][w]で指定してやればポンと
答えが出てくるわけです。

他人が書いたプログラムとはいえよく出来てるなぁ。
うーん、このアルゴリズム考えた人頭いいなぁ。

そして疲れた。