mahmoud-a
8/23/2017 - 11:24 AM

## https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1071

``````#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 1e4;
const int OO = 1e6;

int n, sum = 0, g;
int p[MAX], w[MAX];
int cache[MAX][31];

int knapSack(int i, int rem) {
if(rem == 0 || i == n)
return 0;

int &ret = cache[i][rem];
if(ret != -1)
return ret;

int ch1 = knapSack(i+1, rem);
int ch2 = -1*OO;
if(w[i] <= rem) {
ch2 = knapSack(i+1, rem-w[i]) + p[i];
}

return ret = max(ch1, ch2);
}

int main() {
int t;
cin>>t;
while(t--) {
clr(cache, -1);
sum=0;
cin>>n;
lp(i, n) {
cin>>p[i]>> w[i];
}
cin >> g;
int x;
lp(i, g) {
cin>>x;
sum+=knapSack(0, x);
}
cout << sum << endl;
}

return 0;
}

/*
Similar Problems (from Mustafa Saad Video)
UVA(10130, 10131, 531, 10066, 103, 111, 562, 10819, 10100, 481, 497, 231, 10534, 10192, 10405, 10635, 10949),
LiveArchive(2931),
SRM502-1-2,
SRM395-2-3
*/
``````