Cyber Bird

こちらが俗に言われる「アリ本」こと「プログラミングコンテストチャレンジブック」です。
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分くらいまで短縮できれば、実戦でも使いこなせると思う。