忍者ブログ

Cyber Bird

   

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

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

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

COMMENT

NAME
TITLE
MAIL(非公開)
URL
EMOJI
Vodafone絵文字 i-mode絵文字 Ezweb絵文字
COMMENT
PASS(コメント編集に必須です)
SECRET
管理人のみ閲覧できます

TRACKBACK

Trackback URL:

ブログ内検索

プロフィール

HN:
levelfour
性別:
男性
自己紹介:
ぼちぼち更新を再開する予定です。

twitter

最新コメント

[09/27 菜々氏]
[06/17 NONAME]
[04/30 mithril]
[04/29 Liva]
[01/30 NONAME]

最新トラックバック

コガネモチ

Copyright ©  -- Cyber Bird --  All Rights Reserved
Design by CriCri / Photo by Geralt / powered by NINJA TOOLS / 忍者ブログ / [PR]