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; }