Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int n,gmax;
- float c;
- struct obiect{
- int nr;
- float ef,g,v;}Ob[1001];
- void citire()
- {
- int i;
- cin>>n>>gmax;
- for(i=1;i<=n;i++)
- {cin>>Ob[i].g>>Ob[i].v;
- Ob[i].ef=Ob[i].v/Ob[i].g;
- Ob[i].nr=i;}
- }
- void sortare()
- {
- int i,j;
- for(i=1;i<n;i++)
- for(j=i+1;j<=n;j++)
- if(Ob[i].ef<Ob[j].ef)
- swap(Ob[i],Ob[j]);
- }
- void greedy()
- {
- int i=1;
- while(gmax>0&&i<=n)
- {
- if(Ob[i].g<=gmax)
- {c=c+Ob[i].v;
- gmax=gmax-Ob[i].g;
- }
- else
- {c=c+(gmax/Ob[i].g)*Ob[i].v;
- gmax=0;}
- i++;
- }
- cout<<c;}
- int main()
- {
- citire();
- sortare();
- greedy();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement