UVa-10130 : SuperSale

問題概要

ナップザック。

acceptされたコード

計算量O(N*W)。

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

const int MAX_N = 1000;
const int MAX_G = 100;
const int MAX_W = 30;

int N, G;
int ws[MAX_N], vs[MAX_N], cs[MAX_G];
int dp[MAX_N + 1][MAX_W + 1];

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", vs+i, ws+i);
	}

	scanf("%d", &G);
	for(int i=0; i<G; i++){
		scanf("%d", cs+i);
	}
}

int solve(){
	memset(dp, 0, sizeof(dp));

	for(int i=0; i<N; i++){
		for(int w=0; w <=MAX_W; w++){
			dp[i+1][w] = max(dp[i+1][w], dp[i][w]);
			int nw = w + ws[i];
			if(nw <= MAX_W){
				dp[i+1][nw] = max(dp[i+1][nw], dp[i][w] + vs[i]);
			}
		}
	}

	int ans = 0;
	for(int i=0; i<G; i++){
		ans += dp[N][cs[i]];
	}

	return ans;
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("%d\n", solve());
	}

	return 0;
}