Farid_Mia59

knapsack

Dec 14th, 2019
85
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. float w[100],p[100],x[100];
  4. int n;
  5. class ksack
  6. {
  7. public:
  8. void knapsack(int m,int n)
  9. {
  10. for(int i=1;i<n;i++)
  11. {
  12. int max=i;
  13. for(int j=i+1;j<=n;j++)
  14. {
  15. if((p[j]/w[j])>(p[max]/w[max]))
  16. {
  17. max=j;
  18. }
  19. }
  20. swap(p[max],p[i]);
  21. swap(w[max],w[i]);
  22. }
  23. int u=m;
  24. int i;
  25. for(i=1;i<=n;i++)
  26. {
  27. if(w[i]>u) break;
  28. x[i]=1;
  29. u=u-w[i];
  30. }
  31. if(i<=n)
  32. {
  33. x[i]=u/w[i];
  34. }
  35. }
  36.  
  37. void profit(int n)
  38. {
  39. float sum=0;
  40. for(int i=1;i<=n;i++)
  41. sum+=w[i]*x[i]*p[i];
  42. cout<<endl<<"total profit:"<<sum;
  43. }
  44. };
  45. int main()
  46. {
  47. ksack k;
  48. //int n;
  49. freopen("in.txt","r",stdin);
  50.  
  51. //cout<<"Enter the number of item :";
  52. cin>>n;
  53. //cout<<"Enter the number of profits:";
  54. for(int i=1;i<=n;i++)
  55. {
  56. cin>>p[i]>>w[i];
  57. }
  58. cout<<"number of item:"<<n<<endl;
  59. cout<<"number of profits:";
  60. for(int i=1;i<=n;i++)
  61. {
  62. cout<<p[i]<<" ";
  63. }
  64.  
  65. cout<<endl<<"number of weight:";
  66. for(int i=1;i<=n;i++)
  67. {
  68. cout<<w[i]<<" ";
  69. }
  70. k.knapsack(60,n);
  71. cout<<endl<<"number of profits swap:";
  72. for(int i=1;i<=n;i++)
  73. {
  74. cout<<p[i]<<" ";
  75. }
  76.  
  77. cout<<endl<<"number of weight swap:";
  78. for(int i=1;i<=n;i++)
  79. {
  80. cout<<w[i]<<" ";
  81. }
  82.  
  83. cout<<endl<<"number of portion:";
  84. for(int i=1;i<=n;i++)
  85. {
  86. cout<<x[i]<<" ";
  87. }
  88.  
  89. k.profit(n);
  90. return 0;
  91. }
RAW Paste Data