machi use this.. Define *m*[*i*,*w*] to be the maximum value that can be attained with weight less than or equal to *w* using items up to *i*.
We can define *m*[*i*,*w*] recursively as follows: - [image: m[0,\,w]=0] - [image: m[i,\,0]=0] - [image: m[i,\,w]=m[i-1,\,w]] if [image: w_i>w\,\!] (the new item is more than the current weight limit) - [image: m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)] if [image: w_i \leqslant w]. return m[n,W] where W is the input On Fri, Dec 17, 2010 at 11:38 AM, kumar0746 kerth <kumar0...@gmail.com>wrote: > 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
