01ナップサック問題その2

C++

こちらが俗に言われる「アリ本」こと「プログラミングコンテストチャレンジブック」です。

9/3(土)にパソコン甲子園に出場するのですが…2週間でこの本の初級部分の内容を

身につけて挑むという無謀チャレンジ中です＾＾；







昨年の10月頃に刊行されたようで、プログラミングコンテストで出題される問題を

効率よく制限時間内に解ききるためのアルゴリズムを解説し、問題と解説を載せた

良書です。内容が新しく、主にTopCoderやGoogle Code Jamの問題を取り扱っているようです。

よかったら、みなさんも是非どうぞ。








それでは今回解いた問題です。これからもこんな形式でソースを載せることが

あるのではと思います。





01ナップサック問題その2

重さと価値がそれぞれw[i],v[i]であるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。



　※制約

　・1≦n≦100

　・1≦w[i]≦10^7

　・1≦v[i]≦100

　・1≦W≦10^9



＜入力例＞

4 5 // 4...n(品物の数)、5...W(最大の重さ)

2 3 // 1番目の品物のw,v

1 2 // 2番目の品物のw,v

3 4 // 3番目の品物のw,v

2 2 // 4番目の品物のw,v



＜出力例＞

7



※※若干問題を書き換えている箇所がありますが、問題内容自体は同じです。




ソースコード等は続きに載せる形です。



#include <iostream>

#include <algorithm>

using namespace std;
#define MAXN        100

#define MAXV        100

#define INF                (1<<21)

int w[MAXN], v[MAXN];

int n, W;
main() {

        while(cin >> n >> W && n && W) {

                int d[MAXN+1][MAXN*MAXV+1];

                for(int i = 0; i < n; i++)         cin >> w[i] >> v[i];

                for(int i = 0; i < n; i++)

                        for(int j = 0; j < MAXN*MAXV+1; j++) 

                                d[i][j] = INF;

                

                d[0][0] = 0;

                for(int i = 0; i < n+1; i++) {

                        for(int j = 0; j < MAXN*MAXV+1; j++) {

                                d[i+1][j] = min( d[i][j], d[i][j-v[i]]+w[i] );

                        }

                }

                

                int res;

                for(int i = 0; i < MAXN*MAXV+1; i++) {

                        if(d[n][i] <= W) {

                                res = i;

                        }

                }

                cout << res << endl;

        }

}

こんな感じ。これで19min。

ナップサック問題は動的計画法(DP)の代表例らしい。



本来は、

d[i][j] := i番目までの品物で重さがj以下になるように詰めたときの価値の最大値

と定義するのが妥当で簡単だろうけど、今回はWに10^7までという制約がついているため、

nとWをそれぞれループで回すと計算量がO(nW)、nW=10^9になっちゃうから

1sec以内に実行できない。



そのため、今回は

d[i][j] := i番目までの品物で価値がj以下になるように詰めたときの重さの最小値

と定義して配列dを埋め、d[n][k]==Wとなるkを出力すればおｋ。



漸化式等の説明はちょっと省略。まあそんなに難しくない。



時間はDP使い始めにしてはまあまあじゃないかと思ってるけど、まだまだ短縮の余地がある。

10分くらいまで短縮できれば、実戦でも使いこなせると思う。