uva-10130 (dp)

#include <bits/stdc++.h>
using namespace std;

int cap, n, cost[1005], weight[1005], dp[1005][70];

int obj(int i, int w)
{
    int profit1 = 0, profit2 = 0;
    if(i == n + 1)
    {
        return 0;
    }
    if(w+weight[i] <= cap)
    {
        if(dp[i+1][w + weight[i]] != -1)
        {
            profit1 = cost[i] + dp[i+1][w + weight[i]];
        }
        else
        {
            dp[i+1][w + weight[i]] = obj(i+1, w + weight[i]);
            profit1 = cost[i] + dp[i+1][w + weight[i]];
        }
    }
    if(dp[i+1][w] != -1)
    {
        profit2 = dp[i+1][w];
    }
    else
    {
        dp[i+1][w] = obj(i + 1, w);
        profit2 = dp[i+1][w];
    }

8    return max(profit1, profit2);
}

int main()
{
    int t, p, w, g, mw, i, j, total;
    cin>>t;
    while(t--)
    {
        memset(dp, -1, sizeof(dp));
        cin>>n;
        total = 0;
        for(i = 1; i <= n; i++)
        {
            cin>>cost[i];
            cin>>weight[i];
        }
        cin>>g;
        while(g--)
        {
            cin>>mw;
            cap = mw;
            total += obj(1, 0);
        }
        if(t == 0)
        {
            break;
        }
        cout<<total<<endl;
    }
    cout<<total;
    return 0;
}