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

10130 - SuperSale.cpp

#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
*/