【題目敘述】https://vjudge.net/problem/UVA-10130 (考生答對率: 1.11%)
【解題想法】DP,01背包
#include <iostream>
#include <cstring>
using namespace std;
int T, N, G, MW;
int P[1005], W[1005];
int dp[35];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--){
cin >> N;
for (int i = 0; i < N; i++){
cin >> P[i] >> W[i];
}
cin >> G;
int ans = 0;
while (G--){
cin >> MW;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++){
for (int j = MW; j >= W[i]; j--){
dp[j] = max(dp[j], dp[j - W[i]] + P[i]);
}
}
int mx = 0;
for (int i = 0; i <= MW; i++){
mx = max(mx, dp[i]);
}
ans += mx;
}
cout << ans << "\n";
}
return 0;
}