10130 SuperSaleThere is a SuperSale in a SuperHiperMarket. Every person can take only one object of each kind, i.e.one TV, one carrot, but for extra low price. We are going with a whole family to that SuperHiperMarket.Every person can take as many objects, as he/she can carry out from the SuperSale. We have given listof objects with prices and their weight. We also know, what is the maximum weight that every personcan stand. What is the maximal value of objects we can buy at SuperSale?InputThe input consists of T test cases. The number of them (1 ≤ T ≤ 1000) is given on the first line ofthe input file. Each test case begins with a line containing a single integer number N that indicatesthe number of objects (1 ≤ N ≤ 1000). Then follows N lines, each containing two integers: P and W.The first integer (1 ≤ P ≤ 100) corresponds to the price of object. The second integer (1 ≤ W ≤ 30)corresponds to the weight of object. Next line contains one integer (1 ≤ G ≤ 100) its the number ofpeople in our group. Next G lines contains maximal weight (1 ≤ MW ≤ 30) that can stand this i-thperson from our family (1 ≤ i ≤ G).OutputFor every test case your program has to determine one integer. Print out the maximal value of goodswhich we can buy with that family.Sample Input2372 1744 2331 24126664 2685 2252 499 1839 1354 9423202026Sample Output72514
思路：就是01背包的变种啦，这里相当于有几个背包，，我写的一维的，不知道二维的实现好不好
AC代码：
#include <cstdio>#include <cstring>#include <algorithm> using namespace std;int p[1005], w[1005];int dp[1005];int main() {int T, n, m;scanf("%d", &T);while(T–) {scanf("%d", &n);for(int i = 0; i < n; i++) {scanf("%d%d", &p[i], &w[i]);}int ans = 0;scanf("%d", &m);while(m–) {int bag;scanf("%d", &bag);memset(dp, 0, sizeof(dp));for(int j = 0; j < n; j++) {for(int i = bag; i >= w[j]; i–) {dp[i] = max(dp[i], dp[i-w[j]] + p[j]);}}//printf("%d\n", dp[bag]);ans += dp[bag];}printf("%d\n", ans);}return 0;}
只想到处流浪人生就像一场旅行，不必在乎目的地，
