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

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を出力すればおk。



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



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

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