It’s a well known greedy algorithm, if you are not known with this algo,

You can go through a tutorial ,here is the link

If you are from ,then you should go to Shafaet vaiya’s blog , click it

Implementation of this algorithm

http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/

Now solution of Supersale

## View Code

#include

using namespace std;int knapsack(int W,int wt[],int val[],int n)

{

int i,j;

int k[n+1][W+1];

for(int i=0;i<=n;i++)

{

for(int w=0;w<=W;w++)

{

if(i==0 ||w==0)

k[i][w]=0;

else if(wt[i-1]<=w) k[i][w]=max(val[i-1]+k[i-1][w-wt[i-1]],k[i-1][w]); else k[i][w]=k[i-1][w]; } } return k[n][W]; } int main() { int t; cin>>t;

while(t–){int m,W=-1;

cin>>m;

long long res=0;

int wt[m],val[m];

for(int i=0;i<m;i++) cin>>val[i]>>wt[i];

int n=0;

cin>>n;

while(n–)

{cin>>W;

res+=knapsack(W,wt,val,m);

}cout<<res<<endl;

}

}

- Same Problem

And more

A