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 bangladesh-flag-3d-icon-16 ,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

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized, uva and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s