Advertisement
monyca98

problema rucsacului greedy

May 30th, 2016
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include<fstream>
  2. #include<iostream>
  3. using namespace std;
  4. struct obiect
  5. {   float g,c,e;
  6.     int k;
  7. };
  8. obiect a[20];
  9. int n,m,s[20],G=20;
  10. float x[20];
  11.  
  12. void citire()
  13. {   ifstream f("e:\\info\\greedy\\rucsac.txt");
  14.     f>>n;
  15.     for(int i=1;i<=n;i++)
  16.     {   f>>a[i].k>>a[i].g>>a[i].c;
  17.         a[i].e=a[i].c/a[i].g;}
  18.         f.close();}
  19.  
  20. void afisare()
  21. {   for(int i=1;i<=n;i++)
  22.     {   cout<<a[i].k<<" "<<a[i].g<<" "<<a[i].c<<" "<<a[i].e;
  23.     cout<<endl;}}
  24.  
  25. void sortare()
  26. {   obiect aux;
  27.     for(int i=1;i<n;i++)
  28.         for(int j=i+1;j<=n;j++)
  29.             if(a[i].e<a[j].e)
  30.             {   aux=a[i];
  31.                 a[i]=a[j];
  32.                 a[j]=aux;}}
  33.  
  34. void greedy()
  35. {   int Gr=G,j=0;
  36.     for(int i=1;i<=n && Gr!=0;i++)
  37.         if(Gr>a[i].g)
  38.         {   j++;
  39.             s[j]=i;
  40.             x[j]=1;
  41.             Gr=Gr-a[i].g;}
  42.         else
  43.         {   j++;
  44.             s[j]=i;
  45.             x[j]=Gr/a[i].g;
  46.             Gr=0;}
  47.         m=j;
  48.         cout<<m;}
  49.  
  50. void afisareS()
  51. {   for(int i=1;i<=m;i++)
  52.         cout<<"obiectul nr "<<a[s[i]].k<<" in cantitatea "<<x[i]*a[s[i]].g<<endl;}
  53.  
  54. int main ()
  55. {   citire();
  56.     afisare();
  57.     sortare();
  58.     cout<<endl;
  59.     afisare();
  60.     greedy();
  61.     cout<<endl;
  62.     afisareS();}
  63. 5
  64. 1 5 10
  65. 2 4 20
  66. 3 4 10
  67. 4 8 10
  68. 5 10 22
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement