problem:https://www.spoj.pl/problems/PARTY/
i m getting wrong answer for dis problem.can anyone help me in
finding de mistake..thank u in advance
#include<iostream>
//#include<conio.h>
#include<vector>
#include<algorithm>
using namespace std;
//int n;
int item(int c[][501],int i,int wt,vector<int> &w,int &ans)
{
//int ans;
if(i==0 || wt==0)
return 0;
else
{
if(c[i][wt]==c[i-1][wt])
item(c,i-1,wt,w,ans);
else if(c[i][wt]==c[i][wt-1])
item(c,i,wt-1,w,ans);
else
{
ans=ans+w[i];
item(c,i-1,wt-w[i],w,ans);
// cout<<w[i]<<endl;
// ans+=w[i];
}
}
// return ans;
}
main()
{
int n,tw;
while(cin>>tw>>n && n!=0 && tw!=0){
int i,j,ans=0;
//cin>>n;
vector<int> wt(n+1),v(n+1);
v[0]=wt[0]=0;
int c[501][501];
// cin>>tw;
for(i=1;i<=n;i++)
cin>>wt[i]>>v[i];
for(i=0;i<=tw;i++)
c[0][i]=0;
for(i=1;i<=n;i++)
{
c[i][0]=0;
for(j=1;j<=tw;j++)
{
if(wt[i]<=j)
{
int ma=max(c[i-1][j],c[i][j-1]);
if((v[i]+c[i-1][j-wt[i]])>ma)
c[i][j]=v[i]+c[i-1][j-wt[i]];
else
c[i][j]=ma;
}
else
c[i][j]=max(c[i-1][j],c[i][j-1]);
}
}
// cout<<endl;
item(c,n,tw,wt,ans);
cout<<ans<<" "<<c[n][tw]<<"\n" ;
// cout<<"maximum possible value is"<<c[n][tw];
} //getch();
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
