10130 - SuperSale

Problem Link

This is a classical 0-1 Knapsack Problem.
To solve this problem please read this first.

Now, first try by yourself.
If you get any difficulty , you can get help from my solution...

//Time Complexity O(item * bag_weight * G)
#include<bits/stdc++.h>
using namespace std;

int weight[10000], value[10000];

int knapsack(int bag_weight, int item)
{
    int K[item+1][bag_weight+1];
    for(int i = 0; i <= item; i++)
    {
        for(int w = 0; w <= bag_weight; w++)
        {
            if(i==0 || w==0)
                K[i][w] = 0;
            else if(weight[i-1]<=w)
                K[i][w] = max(K[i-1][w], K[i-1][w-weight[i-1]]+value[i-1]);
            else
                K[i][w] = K[i-1][w];
        }
    }

    return K[item][bag_weight];
}

int main()
{
    int T;
    cin>>T;
    for(int t = 0; t < T; t++)
    {
        int A[31] = {0}, sum = 0;
        int n;
        cin>>n;
        for(int i = 0; i < n; i++)
            cin>>value[i]>>weight[i];
        int G, MG;
        cin>>G;
        for(int i = 0; i < G; i++)
        {
            cin>>MG;
            if(A[MG]==0)
                A[MG] = knapsack(MG,n);
            sum+=A[MG];
        }
        cout<<sum<<endl;
    }
    return 0;
}