裏紙

ほぼ競プロ、たまに日記

AOJ DPL1_B - 0-1 Knapsack Problem

・問題
0-1 Knapsack Problem | Aizu Online Judge

いわゆる普通のナップサック問題。制約とかも普通。

・考え方
dp[i][j]:=品物(i-1)まで入れるかどうか決まっていて、その時の重さがjの時の価値合計の最大値と定義して、全てやり終わった後にdp[N][i]の列をi:0~Wで回して最大値を出そうってやったんだけど、解説(http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=DPL_1_B)を見たら若干考え方が違ったし、こっちはdpを回すだけで終わるのでスマートだなあと思った。
ちなみに解説は大きさjのナップサックに入れられる商品の価値合計の最大値としている。

・実装(C++)

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

int main(){
	int N,W;
	int v[100],w[100];
	
	//input
	scanf(" %d %d", &N, &W);
	for(int i=0; i<N; ++i) scanf(" %d %d", &v[i], &w[i]);
	
	//solve
	
	//dp[i][j]:=品物(i-1)まで入れるかどうか決まっていて、その時の重さがjの時の価値合計の最大値
	int dp[101][10001]={0};
	
	for(int i=0; i<N; ++i){
		for(int j=0; j<=W; ++j){
			if(j-w[i]>=0)
				dp[i+1][j] = max( dp[i][j-w[i]]+v[i], dp[i][j] );
			else dp[i+1][j] = dp[i][j];
		}
	}
	
	int ans=0;
	for(int i=0; i<=W; ++i) ans = max(ans,dp[N][i]);
	printf("%d\n", ans);
}