Advertisement
jakaria_hossain

Fractional Knapsack

Oct 23rd, 2018
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef struct
  4. {
  5. int id;
  6. int wt;
  7. int prc;
  8. float uprc;
  9. }store;
  10. int main()
  11. {
  12. int i,n,j,mxwt;
  13. cin>>n;
  14. store ara[n+1],temp;
  15. for(i=0;i<n;i++)
  16. {
  17. cin>>ara[i].id>>ara[i].wt>>ara[i].prc;
  18. ara[i].uprc=(float)ara[i].prc/(float)ara[i].wt;
  19. }
  20. for(i=0;i<n;i++)
  21. {
  22. for(j=i+1;j<n;j++)
  23. {
  24. if(ara[i].uprc<ara[j].uprc)
  25. {
  26. temp=ara[i];
  27. ara[i]=ara[j];
  28. ara[j]=temp;
  29. }
  30. }
  31. }
  32. cin>>mxwt;
  33. float price=0;
  34. for(i=0;i<n;i++)
  35. {
  36. if(ara[i].wt<=mxwt)
  37. {
  38. mxwt-=ara[i].wt;
  39. price=price+(float)ara[i].wt*ara[i].uprc;
  40. }
  41. if(mxwt==0)break;
  42. else if(ara[i].wt>mxwt)
  43. {
  44. price=price+(float)mxwt*ara[i].uprc;
  45. mxwt-=mxwt;
  46. }
  47.  
  48. }
  49. cout<<endl<<price<<endl;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement