ALGORITHM NOTE こだわり

こだわり

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

問題パソコン甲子園2008 09

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

出典：パソコン甲子園２００８
入力例

出力例

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 : 入力の数列である１次元配列（最初の要素をS[1]とします）
P : P[i] = P[i-1] + S[i] であるような、１次元配列
P[i] には、最初の要素S[1] から S[i] までの合計が記録されています。
M : M[i][j] が 1 から i 番目までの要素を使い S を j 以下の部分に分割したときの最適解（部分の最大値の最小値）を示す２次元配列

(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] の２つの部分に分けたとき、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 の場合は以下の組み合わせが考えられますが、この中で最適なものを選びます。

絵を準備。。。

サンプルプログラム

#include<iostream>
#include<algorithm>
using namespace std;

#define NMAX 100
#define KMAX 100
static const int INFTY = (1<<21);

// n >= k
int compute( int n, int k, int S[NMAX+1] ){

    int M[NMAX+1][KMAX+1], D[NMAX+1][KMAX+1];
    int P[NMAX+1];

    P[0] = 0;
    for ( int i = 1; i <= n; i++ ) P[i] = P[i-1] + S[i];

    for ( int i = 1; i <= n; i++ ) M[i][1] = P[i];
    for ( int j = 1; j <= k; j++ ) M[1][j] = S[1];

    for ( int i = 2; i <= n; i++ ){
        for ( int j = 2; j <= k; j++ ){
            M[i][j] = INFTY;
            for ( int x = 1; x <= i-1; x++ ){
                int maximum = max( M[x][j-1], P[i] - P[x] );
                if ( M[i][j] > maximum ){
                    M[i][j] = maximum;
                    D[i][j] = x;
                }
            }
        }
    }
    return M[n][k];
}

int main(){
    int n, k, S[NMAX+1];
    while(1){
            cin >> k >> n;
            if ( k == 0 && n == 0 ) break;
            for ( int i = 1; i <= n; i++ ) cin >> S[i];
            cout << compute(n, k, S) << endl;
    }
    return 0;
}

スポンサーサイト