Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Apr 25th, 2018 46 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <fstream>
  5. using namespace std;
  6.  
  7. const int inf = 1e9;
  8.  
  9. vector<int> r;
  10. vector<int> d;
  11. vector<int> p;
  12. vector<int> w;
  13. int n;
  14. int t;
  15.  
  16. int penalty(int time, int j)
  17. {
  18.     if (time>d[j])
  19.         return w[j];
  20.     return 0;
  21. }
  22.  
  23. void gen(int nn)
  24. {
  25.     int mod = 10;
  26.     n = nn;
  27.     t = rand()%mod+1;
  28.     r.resize(n);
  29.     d.resize(n);
  30.     p.resize(n);
  31.     w.resize(n);
  32.     for (int i = 0; i<n; i++)
  33.     {
  34.         d[i] = p[i] = w[i] = r[i] =  0;
  35.         if (i)
  36.             r[i] = r[i-1];
  37.         r[i] = r[i] + rand()%mod;
  38.    
  39.         d[i] = r[i] + rand()%mod+1;
  40.         while (i && d[i]<d[i-1])
  41.             d[i] = r[i] + rand()%mod+1;
  42.        
  43.         p[i] = rand()%(d[i]-r[i])+1;
  44.         w[i] = rand()%mod;
  45.     }
  46. }
  47. void read()
  48. {
  49.     cin >> n >> t;
  50.     r.resize(n);
  51.     for (int i = 0; i<n; i++)
  52.         cin >> r[i];
  53.     d.resize(n);
  54.     for (int i = 0; i<n; i++)
  55.         cin >> d[i];
  56.     p.resize(n);
  57.     for (int i = 0; i<n; i++)
  58.         cin >> p[i];
  59.     w.resize(n);
  60.     for (int i = 0; i<n; i++)
  61.         cin >> w[i];
  62.    
  63. }
  64. bool readfromfile()
  65. {
  66.     cout << "Введите путь к файлу: ";
  67.     string s;
  68.     cin >> s;
  69.     ifstream fin(s);
  70.     if (!(fin >> n >> t))
  71.         return false;;
  72.     r.resize(n);
  73.     for (int i = 0; i<n; i++)
  74.         if (!(fin >> r[i]))
  75.             return false;
  76.     d.resize(n);
  77.     for (int i = 0; i<n; i++)
  78.         if (!(fin >> d[i]))
  79.             return false;
  80.     p.resize(n);
  81.     for (int i = 0; i<n; i++)
  82.         if (!(fin >> p[i]))
  83.             return false;
  84.     w.resize(n);
  85.     for (int i = 0; i<n; i++)
  86.         if (!(fin >> w[i]))
  87.             return false;
  88.     return true;
  89. }
  90.  
  91. int calcT(vector<int> &v, int t, int without)
  92. {
  93.     int curtime = t;
  94.     for (int i = 0; i<v.size(); i++)
  95.     {
  96.         if (v[i] == without)
  97.             continue;
  98.        
  99.         curtime = max(curtime,r[v[i]]);
  100.         curtime+= p[v[i]];
  101.        
  102.     }
  103.     return curtime;
  104. }
  105. pair<vector<int>,vector<int>> algo()
  106. {
  107.     int curtime = t;
  108.     vector<int> late,notlate;
  109.     queue<int> todo;
  110.     for (int i = 0; i<n; i++)
  111.         todo.push(i);
  112.     while (!todo.empty())
  113.     {
  114.        
  115.         int i = todo.front();
  116.         curtime = max(curtime,r[i]);
  117.         if (curtime+p[i]<=d[i]) // если не запаздывает добавляем в множество незапаздывающих
  118.         {
  119.             notlate.push_back(i);
  120.             curtime+=p[i];
  121.             todo.pop();
  122.         }
  123.         else
  124.         {
  125.             int m = i;
  126.             int mintime = INT_MAX;
  127.             notlate.push_back(i);
  128.             for (int j = 0; j<notlate.size(); j++)
  129.             {
  130.                 int calct = calcT(notlate,t,notlate[j]);
  131.                 if (calct<mintime)
  132.                 {
  133.                     m = j;
  134.                     mintime = calct;
  135.                 }
  136.             }
  137.             notlate.pop_back();
  138.             if (notlate[m] == i)
  139.             {
  140.                 late.push_back(i);
  141.                 todo.pop();
  142.             }
  143.             else
  144.             {
  145.                 late.push_back(notlate[m]);
  146.                 notlate.erase(notlate.begin()+m);
  147.                 curtime = calcT(notlate, t, inf);
  148.             }
  149.         }
  150.     }
  151.     return {notlate,late};
  152. }
  153. int calcF(vector<int> &late)
  154. {
  155.     int ans = 0;
  156.     for (auto it:late)
  157.         ans+=w[it];
  158.     return ans;
  159. }
  160. void update(pair<vector<int>,vector<int>> &best, vector<int>&late, vector<int> &notlate)
  161. {
  162.     if (best.first.size()==0 && best.second.size()==0)
  163.     {
  164.         best = {notlate,late};
  165.         return;
  166.     }
  167.     if (calcF(best.second)>calcF(late))
  168.     {
  169.         best = {notlate,late};
  170.     }
  171. }
  172.  
  173. pair<vector<int>,vector<int>> bestSol()
  174. {
  175.     vector<int> perm;
  176.     for (int i = 0; i<n; i++)
  177.     {
  178.         perm.push_back(i);
  179.     }
  180.    
  181.     pair<vector<int>,vector<int>> best;// первое значение незапаздывающие второе запаздывающие
  182.     do
  183.     {
  184.         int curtime = t;
  185.         vector<int> late,notlate;
  186.         for (auto it:perm)
  187.         {
  188.             int i = it;
  189.             curtime = max(curtime,r[i]);
  190.             if (curtime+p[i]<=d[i])
  191.             {
  192.                 notlate.push_back(i);
  193.                 curtime+=p[i];
  194.             }
  195.             else
  196.             {
  197.                 late.push_back(i);
  198.             }
  199.         }
  200.         update(best,late,notlate);
  201.     }
  202.     while (next_permutation(perm.begin(),perm.end()));
  203.     return best;
  204. }
  205.  
  206. pair<vector<int>,vector<int>> algo1()// не учитываем веса, если не нашлось требования удовлетворяющее двум условиям
  207. {
  208.     int curtime = t;
  209.     vector<int> late,notlate;
  210.     queue<int> todo;
  211.     for (int i = 0; i<n; i++)
  212.         todo.push(i);
  213.     while (!todo.empty())
  214.     {
  215.        
  216.         int i = todo.front();
  217.         curtime = max(curtime,r[i]);
  218.         if (curtime+p[i]<=d[i]) // если не запаздывает добавляем в множество незапаздывающих
  219.         {
  220.             notlate.push_back(i);
  221.             curtime+=p[i];
  222.             todo.pop();
  223.         }
  224.         else
  225.         {
  226.             int mintimeind = 0;
  227.             int minwind = 0;
  228.             notlate.push_back(i);
  229.             vector<pair<int,int>> forcalc(notlate.size());
  230.            
  231.             for (int j = 0; j<notlate.size(); j++)
  232.             {
  233.                 forcalc[j] = {calcT(notlate,t,notlate[j]),w[notlate[j]]};
  234.                 if (forcalc[mintimeind].first>forcalc[j].first)
  235.                     mintimeind = j;
  236.                 if (forcalc[minwind].second>forcalc[j].second)
  237.                     minwind = j;
  238.             }
  239.             notlate.pop_back();
  240.  
  241.             int m = -1;
  242.            
  243.             for(int j = 0; j<notlate.size(); j++)
  244.                 if (forcalc[j].first == forcalc[mintimeind].first && forcalc[j].second == forcalc[minwind].second)
  245.                     m = j;
  246.             if (m==-1)// тут мы не смогли найти требование которое удовлетворяет двум условиям, берем то у которого минимальное время и среди всех таких мин вес
  247.             {
  248.                 m = mintimeind;
  249.                 for (int j = 0; j<notlate.size(); j++)
  250.                     if (forcalc[j].first == forcalc[m].first && forcalc[j].second<forcalc[m].second)
  251.                         m = j;
  252.             }
  253.            
  254.             if (notlate[m] == i)
  255.             {
  256.                 late.push_back(i);
  257.                 todo.pop();
  258.             }
  259.             else
  260.             {
  261.                 late.push_back(notlate[m]);
  262.                 notlate.erase(notlate.begin()+m);
  263.                 curtime = calcT(notlate, t, inf);
  264.             }
  265.         }
  266.     }
  267.     return {notlate,late};
  268. }
  269.  
  270.  
  271. pair<vector<int>,vector<int>> algo2()// учитываем веса, если не нашлось требования удовлетворяющее двум условиям
  272. {
  273.     int curtime = t;
  274.     vector<int> late,notlate;
  275.     queue<int> todo;
  276.     for (int i = 0; i<n; i++)
  277.         todo.push(i);
  278.     while (!todo.empty())
  279.     {
  280.        
  281.         int i = todo.front();
  282.         curtime = max(curtime,r[i]);
  283.         if (curtime+p[i]<=d[i]) // если не запаздывает добавляем в множество незапаздывающих
  284.         {
  285.             notlate.push_back(i);
  286.             curtime+=p[i];
  287.             todo.pop();
  288.         }
  289.         else
  290.         {
  291.             int mintimeind = 0;
  292.             int minwind = 0;
  293.             notlate.push_back(i);
  294.             vector<pair<int,int>> forcalc(notlate.size());
  295.            
  296.             for (int j = 0; j<notlate.size(); j++)
  297.             {
  298.                 forcalc[j] = {calcT(notlate,t,notlate[j]),w[notlate[j]]};
  299.                 if (forcalc[mintimeind].first>forcalc[j].first)
  300.                     mintimeind = j;
  301.                 if (forcalc[minwind].second>forcalc[j].second)
  302.                     minwind = j;
  303.             }
  304.             notlate.pop_back();
  305.            
  306.             int m = -1;
  307.            
  308.             for(int j = 0; j<notlate.size(); j++)
  309.                 if (forcalc[j].first == forcalc[mintimeind].first && forcalc[j].second == forcalc[minwind].second)
  310.                     m = j;
  311.             if (m==-1)// тут мы не смогли найти требование которое удовлетворяет двум условиям, берем то у которого мин вес и среди всех таких мин время
  312.             {
  313.                 m = minwind;
  314.                 for (int j = 0; j<notlate.size(); j++)
  315.                     if (forcalc[j].second == forcalc[m].second && forcalc[j].first<forcalc[m].first)
  316.                         m = j;
  317.             }
  318.            
  319.             if (notlate[m] == i)
  320.             {
  321.                 late.push_back(i);
  322.                 todo.pop();
  323.             }
  324.             else
  325.             {
  326.                 late.push_back(notlate[m]);
  327.                 notlate.erase(notlate.begin()+m);
  328.                 curtime = calcT(notlate, t, inf);
  329.             }
  330.         }
  331.     }
  332.     return {notlate,late};
  333. }
  334.  
  335. bool issled = false;
  336. int bettersolution[2];
  337. void solve(int disp)
  338. {
  339.    // debug();
  340.     auto ans = algo();
  341.     if (disp)
  342.     {
  343.         cout << "Результат работы алгоритма из лекции\n";
  344.         cout << "Незапаздывающие: ";
  345.         for (auto it: ans.first)
  346.             cout << it+1 << " ";
  347.         cout << endl << "Запаздывающие: ";
  348.         for (auto it:ans.second)
  349.             cout << it+1 << " ";
  350.        
  351.         cout << "\nСумма весов запаздывающих: " << calcF(ans.second) << endl << endl;
  352.     }
  353.    
  354.     auto ans1 = algo1();
  355.     if (disp)
  356.     {
  357.         cout << "Результат работы алгоритма с учетом первого условия\n";
  358.         cout << "Незапаздывающие: ";
  359.         for (auto it: ans1.first)
  360.             cout << it+1 << " ";
  361.         cout << endl << "Запаздывающие: ";
  362.         for (auto it:ans1.second)
  363.             cout << it+1 << " ";
  364.        
  365.         cout << "\nСумма весов запаздывающих: " << calcF(ans1.second) << endl << endl;
  366.     }
  367.     auto ans3 = algo2();
  368.     if (disp)
  369.     {
  370.         cout << "Результат работы алгоритма с учетом второго условия\n";
  371.         cout << "Незапаздывающие: ";
  372.         for (auto it: ans3.first)
  373.             cout << it+1 << " ";
  374.         cout << endl << "Запаздывающие: ";
  375.         for (auto it:ans3.second)
  376.             cout << it+1 << " ";
  377.        
  378.         cout << "\nСумма весов запаздывающих: " << calcF(ans3.second) << endl << endl;
  379.    
  380.     }
  381.     if (n<10)
  382.     {
  383.         auto ans2 = bestSol();
  384.         if (disp)
  385.         {
  386.             cout << "Результат работы точного алгоритма\n";
  387.             cout << "Незапаздывающие: ";
  388.             for (auto it: ans2.first)
  389.                 cout << it+1 << " ";
  390.             cout << endl << "Запаздывающие: ";
  391.             for (auto it:ans2.second)
  392.                 cout << it+1 << " ";
  393.            
  394.             cout << "\nСумма весов запаздывающих: " << calcF(ans2.second) << endl;
  395.         }
  396.     }
  397.     if (issled)
  398.     {
  399.         int second = calcF(ans3.second);
  400.         int first = calcF(ans1.second);
  401.         int best = min(first,second);
  402.         if (first == best)
  403.         {
  404.             bettersolution[0]++;
  405.             if (disp)
  406.             {
  407.                 cout << "Алгоритм с учетом первого условия хорошо отработал для данной задачи\n";
  408.             }
  409.         }
  410.         if (second == best)
  411.         {
  412.             bettersolution[1]++;
  413.             if (disp)
  414.             {
  415.                 cout << "Алгоритм с учетом второго условия хорошо отработал для данной задачи\n";
  416.             }
  417.         }
  418.     }
  419.    
  420. }
  421.  
  422. void display()
  423. {
  424.     cout << n << " "<< t << endl;
  425.     for (int i = 0; i<n; i++)
  426.         cout << r[i] << " ";
  427.     cout << endl;
  428.     for (int i = 0; i<n; i++)
  429.         cout << d[i] << " ";
  430.     cout << endl;
  431.     for (int i = 0; i<n; i++)
  432.         cout << p[i] << " ";
  433.     cout << endl;
  434.     for (int i = 0; i<n; i++)
  435.         cout << w[i] << " ";
  436.     cout << endl;
  437. }
  438. int get_command()
  439. {
  440.     int x = -1;
  441.     while (x<0 || x>3)
  442.     {
  443.         cout << "Введите 1 для проведения иследование\n        2 для ввода данных с файла\n        3 для ввода данных вручную\n        0 для выхода\n";
  444.         cin >> x;
  445.     }
  446.     return x;
  447. }
  448. void make_isledovanie()
  449. {
  450.     issled = true;
  451.     cout << "Введите количество тестов: ";
  452.     int tests;
  453.     cin >> tests;
  454.     bettersolution[0] = bettersolution[1] = 0;
  455.     int disp = 2;
  456.     while (disp!=0 && disp!=1)
  457.     {
  458.         cout << "Для просмотра решения каждого примера нажмите 1, иначе 0: ";
  459.         cin >> disp;
  460.     }
  461.     int nn = 0;
  462.     for (int i = 0; i<tests; i++)
  463.     {
  464.         if(i%5==0)
  465.             nn+=5;
  466.         gen(nn);
  467.         if (disp)
  468.             display();
  469.         solve(disp);
  470.     }
  471.     cout << "Алгоритм с учетом первого условия хорошо отработал для "<< bettersolution[0]*100.0/nn<<"% задач\n";
  472.     cout << "Алгоритм с учетом второго условия хорошо отработал для "<< bettersolution[1]*100.0/nn<<"% задач\n";
  473.  
  474.     issled = false;
  475. }
  476.  
  477. int main()
  478. {
  479.     srand(time(0));
  480.     while (true) {
  481.         int x = get_command();
  482.         if (x==0)
  483.             break;
  484.         if (x==1)
  485.         {
  486.             make_isledovanie();
  487.         }
  488.         else if (x == 2)
  489.         {
  490.             bool readed = readfromfile();
  491.             if (!readed)
  492.             {
  493.                 cout << "Неправильный путь или неверные входные данные в файле. Повторите еще раз";
  494.                 continue;
  495.             }
  496.             display();
  497.             solve(1);
  498.         }
  499.         else
  500.         {
  501.             read();
  502.             solve(1);
  503.         }
  504.     }
  505.    
  506. }
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