Advertisement
Guest User

Untitled

a guest
May 25th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.72 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement