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