fc2ブログ



こだわり

2008.09.15 13:58  パソコン甲子園 2008

問題 パソコン甲子園2008 09

厚さが異なる n 冊の本を、 k 段の本棚に入れるとき、本棚の最小の幅を求めて下さい。

pck200809.gif
出典:パソコン甲子園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]は以下のようになります。
123
1555
2855
31688
418108
519118
625169
7341815
8412216
9452518

例えば i = 6, j = 3 の場合は以下の組み合わせが考えられますが、この中で最適なものを選びます。


絵を準備。。。

サンプルプログラム

スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ