こだわり
2008.09.15 13:58 パソコン甲子園 2008
問題 パソコン甲子園2008 09
厚さが異なる n 冊の本を、 k 段の本棚に入れるとき、本棚の最小の幅を求めて下さい。

出典:パソコン甲子園2008
入力例
出力例
厚さが異なる n 冊の本を、 k 段の本棚に入れるとき、本棚の最小の幅を求めて下さい。

出典:パソコン甲子園2008
入力例
3 9 500 300 800 200 100 600 900 700 400 4 3 1000 1000 1000 0 0
出力例
1800 1000
解説
Partition Problem といいます。
[この問題では、本の厚さの制限が緩いので、力任せ(本棚の幅を少しづづ厚くしていき貪欲に解く)で解けたのかもしれませんが、点数から察して、悲しいことに設定ミスか、または意図的に難易度を下げたか、または実行時間の制限を厳しくしているのでしょうか。力任せで解けないのであれば難易度はさらに高くなります。]
出題者が求めた解法は、動的計画法または二分法だと思います。
ここでは、動的計画法でこの Partition Problem を解きます。
Partition Problem とは、n 個の数からなる数列
S = {s1, ..... sn}
を k 個の部分に分割するときに、各部分の数字の和をできるだけ均等にする、という問題です。厳密に言えば、各部分の数字の和の最大値を最小にするような分割を行います。
例えば、k が 3 の場合、数列
5 3 8 2 1 6 9 7 4
は
5 3 8 | 2 1 6 | 9 7 4
と 3 つに分割することができます(これは最適な解ではありません)。
この場合は各部分の合計は、16, 9, 20 となり、その最大は 20 となります。
ところが、同じ数列を
5 3 8 | 2 1 6 9 | 7 4
と分割すれば、各部分の合計は 16, 18, 11 となり、その最大が 18 となります。そしてこれが最適解となります(最大値が 18 を下回る分割方法はない)。
仮にこの問題を nCk の組み合わせで総当たりに計算しても、本棚の厚みを少しづつ増やしていく方法で反復的に計算しても、その計算量は膨大になります。
では、動的計画法で解いてみましょう。
まず、以下のデータを用意します。
S : 入力の数列である1次元配列 (最初の要素をS[1]とします)
P : P[i] = P[i-1] + S[i] であるような、1次元配列
P[i] には、最初の要素S[1] から S[i] までの合計が記録されています。
M : M[i][j] が 1 から i 番目までの要素を使い S を j 以下の部分に分割したときの最適解(部分の最大値の最小値)を示す2次元配列
(1) j = 1 の場合、1 ~ i までの要素を 1 個に分割するので、
M[i][1] = P[i] (i = 1,,,n)
となります。
(2) i = 1 の場合、1 つの要素を j 個に分割するので、
M[1][j] = S[1] (j = 1,,,k)
となります。
(3) 2 <= i, 2 <= j の場合 M[i][j] は
x が 1 から i-1 について、S[1] ~ S[i] を S[1] ~ S[x] と S[x+1] ~ S[i] の2つの部分に分けたとき、M[x][j-1] と P[i] - P[x] の大きい方が最小になるような x での最小値になります。ここで、M[x][j-1] は、1 から x 番目までの要素を使い S を j-1 個の部分に分割したときの最適解、
P[i] - P[x] は、x+1 から i 番目までの要素を1つの部分とした場合の合計値
を示します。上記のデータを例にとると、M[i][j]は以下のようになります。
1 | 2 | 3 | |
1 | 5 | 5 | 5 |
2 | 8 | 5 | 5 |
3 | 16 | 8 | 8 |
4 | 18 | 10 | 8 |
5 | 19 | 11 | 8 |
6 | 25 | 16 | 9 |
7 | 34 | 18 | 15 |
8 | 41 | 22 | 16 |
9 | 45 | 25 | 18 |
例えば i = 6, j = 3 の場合は以下の組み合わせが考えられますが、この中で最適なものを選びます。
絵を準備。。。
サンプルプログラム
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |