0-1 Knapsack Problem / UVa 10130

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

Click this

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

→  The Knapsack

→ Large Knapsack

And more

A

 

Advertisements