SHARE
TWEET

Untitled

a guest May 25th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6.  
  7. #define INT_MAX 10000000
  8.  
  9. using namespace std;
  10.  
  11. int n,m;
  12.  
  13. class Quest
  14. {
  15. public:
  16.     int task_number;
  17.     int sum_of_times;
  18.  
  19.     vector<int> time_exec;
  20.     vector<int> start_quest;
  21.  
  22.     void count_sum();
  23.  
  24.     bool operator < (const Quest& q) const
  25.     {
  26.        return sum_of_times > q.sum_of_times;
  27.     }
  28. };
  29.  
  30. void Quest::count_sum()
  31. {
  32.      int i;
  33.       sum_of_times = 0;
  34.  
  35.      for(i=0; i< time_exec.size(); i++)
  36.      {
  37.           sum_of_times += time_exec[i];
  38.      }
  39.  
  40. }
  41.  
  42. class NEH
  43. {
  44. public:
  45.  
  46.      vector<Quest> quest1;
  47.      vector<Quest> quest2;
  48.  
  49.      bool load_file();
  50.      void algorithmNEH();
  51.      void find_Cmax();
  52.      void show(vector<Quest> &quest);
  53.      int Cmax;
  54.  
  55. };
  56.  
  57. void NEH::show(vector<Quest> &quest)
  58. {
  59.      int i=0,j=0;
  60.      for( i=0; i<quest.size(); i++)
  61.      {
  62.           for( j=0; j<m; j++)
  63.           {
  64.                cout << quest[i].time_exec[j] << " ";
  65.           }
  66.           if(quest.size() == quest1.size())
  67.                cout << "Suma: " << quest[i].sum_of_times << endl;
  68.           else
  69.                cout << endl;
  70.      }
  71. }
  72.  
  73.  
  74. bool NEH::load_file()
  75. {
  76.      int i=0,j=0;
  77.      int time;
  78.      Quest tmp;
  79.  
  80.     ifstream file;
  81.     file.open("NEH7.DAT", ios::in);
  82.     file >> n >> m;
  83.  
  84.     for(i=0; i<n; i++)
  85.      {
  86.           tmp.task_number = i+1;
  87.           quest1.push_back(tmp);
  88.  
  89.           for(j=0; j<m; j++)
  90.           {
  91.                file >> time;
  92.                quest1[i].time_exec.push_back(time);
  93.           }
  94.           quest1[i].count_sum();
  95.  
  96.      }
  97.      return true;
  98. }
  99.  
  100. void NEH::find_Cmax()
  101. {
  102.      int bestCmax=INT_MAX;
  103.      int position=0;
  104.      Cmax=INT_MAX;
  105.      int left=0,right=0;
  106.      int i=0;
  107.      int j=0;
  108.      int tmp=0;
  109.  
  110.      for(tmp=0; tmp<quest2.size(); tmp++)
  111.      {
  112.           quest2[0].start_quest.push_back(0);
  113.  
  114.           for(i=0; i<m-1; i++)
  115.           {
  116.                quest2[0].start_quest.push_back(quest2[0].start_quest[i] + quest2[0].time_exec[i]);
  117.           }
  118.  
  119.           for(i=1; i<quest2.size(); i++)
  120.           {
  121.                quest2[i].start_quest.push_back(quest2[i-1].start_quest[0] + quest2[i-1].time_exec[0]);
  122.           }
  123.  
  124.           for(j=1; j<quest2.size(); j++)
  125.           {
  126.                for(i=1; i<m; i++)
  127.                {
  128.                     quest2[j].start_quest.push_back(max(quest2[j-1].time_exec[i] + quest2[j-1].start_quest[i], quest2[j].time_exec[i-1] + quest2[j].start_quest[i-1]));
  129.                }
  130.           }
  131.  
  132.           Cmax = (quest2.back().start_quest.back() + quest2.back().time_exec.back());
  133.  
  134.           cout << "Cmax = " << Cmax << endl;
  135.  
  136.           for(i=0; i<quest2.size(); i++)
  137.           {
  138.                quest2[i].start_quest.clear();
  139.           }
  140.  
  141.           if(Cmax < bestCmax)
  142.           {
  143.               bestCmax = Cmax;
  144.               position=0;
  145.           }
  146.           else
  147.           {
  148.                position++;
  149.           }
  150.  
  151.           right = quest2.size() - tmp -1;
  152.           left = quest2.size() - tmp -2;
  153.  
  154.           if(tmp < quest2.size()-1)
  155.           {
  156.                swap(quest2[left],quest2[right]);
  157.           }
  158.      }
  159.      for(i=0; i<position; i++)
  160.      {
  161.           swap(quest2[i], quest2[i+1]);
  162.      }
  163.  
  164.      Cmax = bestCmax;
  165.  
  166.  
  167. }
  168.  
  169. void NEH::algorithmNEH()
  170. {
  171.      int i=0;
  172.      int tmp[2];
  173.      int a=0,b=0;
  174.  
  175.  
  176.      sort(quest1.begin(), quest1.end());
  177.      cout << "Posortowane wedlug sumy:" << endl;
  178.  
  179.      show(quest1);
  180.      quest2.push_back(quest1[0]);
  181.      quest2.push_back(quest1[1]);
  182.  
  183.           for(a=0; a<quest2.size(); a++)
  184.      {
  185.           quest2[0].start_quest.push_back(0);
  186.           quest2[1].start_quest.push_back(quest2[0].start_quest[0] + quest2[0].time_exec[0]);
  187.  
  188.           for(b=0; b<m-1; b++)
  189.           {
  190.                quest2[0].start_quest.push_back(quest2[0].start_quest[b] + quest2[0].time_exec[b]);
  191.           }
  192.  
  193.           for(b=1; b<m; b++)
  194.           {
  195.                quest2[1].start_quest.push_back(max(quest2[1].time_exec[b-1], quest2[0].time_exec[b] + quest2[0].start_quest[b]));
  196.           }
  197.  
  198.           Cmax= quest2.back().start_quest.back() + quest2.back().time_exec.back();
  199.  
  200.           tmp[a] = Cmax;
  201.  
  202.           quest2[0].start_quest.clear();
  203.           quest2[1].start_quest.clear();
  204.           swap(quest2[0],quest2[1]);
  205.  
  206.      }
  207.  
  208.      if(tmp[0] > tmp[1])
  209.      {
  210.           Cmax = tmp[1];
  211.           swap(quest2[0],quest2[1]);
  212.      }
  213.      else
  214.      {
  215.           Cmax = tmp[0];
  216.      }
  217.  
  218. for(i = 2; i<n; i++)
  219. {
  220.      quest2.push_back(quest1[i]);
  221.      find_Cmax();
  222.  
  223. }
  224. }
  225.  
  226.  
  227.  
  228. int main()
  229. {
  230.      NEH ob;
  231.  
  232.      ob.load_file();
  233.      ob.show(ob.quest1);
  234.      ob.algorithmNEH();
  235.  
  236.      cout << "Cmax ostateczny: " << ob.Cmax << endl;
  237.  
  238.      return 0;
  239. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top