Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.76 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. int n,gmax;
  4. float c;
  5. struct obiect{
  6. int nr;
  7. float ef,g,v;}Ob[1001];
  8. void citire()
  9. {
  10. int i;
  11. cin>>n>>gmax;
  12. for(i=1;i<=n;i++)
  13. {cin>>Ob[i].g>>Ob[i].v;
  14. Ob[i].ef=Ob[i].v/Ob[i].g;
  15. Ob[i].nr=i;}
  16. }
  17. void sortare()
  18. {
  19. int i,j;
  20. for(i=1;i<n;i++)
  21. for(j=i+1;j<=n;j++)
  22. if(Ob[i].ef<Ob[j].ef)
  23. swap(Ob[i],Ob[j]);
  24. }
  25. void greedy()
  26. {
  27. int i=1;
  28. while(gmax>0&&i<=n)
  29. {
  30. if(Ob[i].g<=gmax)
  31. {c=c+Ob[i].v;
  32. gmax=gmax-Ob[i].g;
  33. }
  34. else
  35. {c=c+(gmax/Ob[i].g)*Ob[i].v;
  36. gmax=0;}
  37. i++;
  38. }
  39. cout<<c;}
  40. int main()
  41. {
  42. citire();
  43. sortare();
  44. greedy();
  45. return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement