题目大意：商场进行促销活动，有n件商品，给出每件商品的重量和价格。一家人去购物，每个人只能搬运wi重量的物品，而且每种商品只能购买一件，问这家人最多能买多少钱的商品。典型的0-1背包问题。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 int p[1010], w[1010]; 6 int dp[1010][35]; 7 8 int main() 9 { 10 #ifdef LOCAL 11 freopen("in", "r", stdin); 12 #endif 13 int T; 14 scanf("%d", &T); 15 while (T--) 16 { 17 int n; 18 scanf("%d", &n); 19 for (int i = 1; i <= n; i++) 20 scanf("%d%d", &p[i], &w[i]); 21 int k, sum = 0; 22 scanf("%d", &k); 23 while (k--) 24 { 25 int x; 26 scanf("%d", &x); 27 for (int i = 0; i <= 30; i++) 28 dp[0][i] = 0; 29 for (int i = 1; i <= n; i++) 30 for (int j = 0; j <= x; j++) 31 { 32 dp[i][j] = dp[i-1][j]; 33 if (j >= w[i]) 34 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]); 35 } 36 sum += dp[n][x]; 37 } 38 printf("%d ", sum); 39 } 40 return 0; 41 }