Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int vi[10],wi[10],n;
- int c[100][100];
- int wt=0,bt=0;
- int show(int i,int k);
- int main()
- {
- int i,j,k;
- cin>>n;
- for(i=1;i<=n;i++)
- {
- cin>>wi[i]>>vi[i];
- }
- int mw;
- cin>>mw;
- for(i=0;i<=n;i++)
- {
- c[i][0]=0;
- }
- for(i=0;i<=mw;i++)
- {
- c[0][i]=0;
- }
- int w;
- for(i=1;i<=n;i++)
- {
- for(w=1;w<=mw;w++)
- {
- if(wi[i]>w)
- {
- c[i][w]=c[i-1][w];
- }
- else
- {
- c[i][w]=max(c[i-1][w],c[i-1][w-wi[i]]+vi[i]);
- }
- }
- }
- // for(i=0;i<=n;i++)
- // {
- // for(j=0;j<=mw;j++)
- // {
- // cout<<c[i][j]<<"\t";
- // }
- // cout<<endl;
- // }
- cout<<"Item"<<"\t"<<"weight"<<"\t"<<"benefit"<<endl;
- show(n,mw);
- return 0;
- }
- int show(int i,int k)
- {
- if(i==0)
- {
- cout<<endl<<"total weight:"<<wt<<"\t"<<"total benefit:"<<bt<<endl;
- return 0;
- }
- else if(c[i][k]==c[i-1][k])
- {
- show(i-1,k);
- }
- else
- {
- cout<<i<<"\t"<<wi[i]<<"\t"<<vi[i]<<endl;
- wt+=wi[i];
- bt+=vi[i];
- show(i-1,k-wi[i-1]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement