fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. #include <algorithm>
  5. #include <iterator>
  6. #include <tuple>
  7. #include <numeric>
  8.  
  9. using namespace std;
  10.  
  11. namespace {
  12.  
  13.     void PrintArray(const vector<unsigned long> &a, const vector<int> &indexes, bool first) {
  14.         string s = (first ? "First" : "Second");
  15.  
  16.         cout << s << "Shares: [";
  17.  
  18.         unsigned long sum = 0;
  19.  
  20.         for (auto i : indexes) {
  21.             sum += a[i];
  22.             cout << a[i] << ",";
  23.         }
  24.  
  25.         cout << "] " << s << "TotalValue: ";
  26.  
  27.         cout << sum << endl;
  28.     }
  29.  
  30.     vector<int> BuilArrayByMask(unsigned long size, unsigned long mask) {
  31.         vector<int> result;
  32.         int index = 1;
  33.         while (size && mask) {
  34.             if (mask & 1) {
  35.                 result.push_back(index - 1);
  36.             }
  37.             index += 1;
  38.             mask >>= 1;
  39.             --size;
  40.         }
  41.         return result;
  42.     }
  43.  
  44.     unsigned long ScoreArray(const vector<unsigned long> &a, unsigned long i) {
  45.         unsigned long res = 0;
  46.         unsigned long j = 0;
  47.         while (i != 0) {
  48.             unsigned long mask = (unsigned long) 1 << j;
  49.             if (i & mask) {
  50.                 res += a[j];
  51.                 i ^= mask;
  52.             }
  53.             ++j;
  54.         }
  55.         return res;
  56.     }
  57. }
  58.  
  59. // Генерируем все маски длины n бит и для каждой маски (разбиения)
  60. // считаем ее цену. Сложность O(n*2^n) Цена второго разбиения
  61. // получается овтоматически. Дальше сравниваем разность разбиения
  62. // и выбираем лучшее
  63.  
  64. struct SolveBruteIterative
  65. {
  66.  
  67.     void Solve(const vector<unsigned long> &a) {
  68.         auto min_diff = std::numeric_limits<unsigned long>::max();
  69.         unsigned long first_mask = 0;
  70.         unsigned long second_mask = 0;
  71.  
  72.         auto total = std::accumulate(a.begin(), a.end(), (unsigned long) 0);
  73.  
  74.         const auto N = a.size();
  75.  
  76.         for (unsigned long i = 0; i < (1 << (N + 1)); ++i) {
  77.             long long f = ScoreArray(a, i);
  78.             long long s = total - f;
  79.             if (abs(f - s) < min_diff) {
  80.                 min_diff = abs(f - s);
  81.                 first_mask = i;
  82.                 second_mask = ~i;
  83.             }
  84.         }
  85.  
  86.         PrintArray(a, BuilArrayByMask(N, first_mask), true);
  87.         PrintArray(a, BuilArrayByMask(N, second_mask), false);
  88.     }
  89. };
  90.  
  91. // Рекурсивно генерируем все подмножества и выбираем наилучшее разбиение
  92. // Сложность - очевидно O(2^n)
  93. // По сравнению с предыдущим вариантом не надо бегать по маскам для вычисления
  94. // цены разбиения
  95.  
  96. struct SolveBruteRecursive
  97. {
  98. private:
  99.     struct TaskInfo {
  100.         unsigned long min_diff = std::numeric_limits<unsigned long>::max();
  101.         vector<int> first;
  102.         vector<int> second;
  103.         unsigned long total = 0;
  104.     } t;
  105.  
  106.     void Solve(
  107.         const vector<unsigned long> &a,
  108.         unsigned long i,
  109.         vector<int> &left_prefix,
  110.         vector<int> &right_prefix,
  111.         unsigned long prefix_sum) {
  112.         if (i < a.size()) {
  113.             right_prefix.push_back(i);
  114.             Solve(a, i + 1, left_prefix, right_prefix, prefix_sum);
  115.             right_prefix.pop_back();
  116.             left_prefix.push_back(i);
  117.             Solve(a, i + 1, left_prefix, right_prefix, prefix_sum + a[i]);
  118.             left_prefix.pop_back();
  119.         } else {
  120.             if (abs((long) t.total - 2 * (long) prefix_sum) < t.min_diff) {
  121.                 t.min_diff = (unsigned long) (abs((long) t.total - 2 * (long) prefix_sum));
  122.                 t.first = left_prefix;
  123.                 t.second = right_prefix;
  124.             }
  125.         }
  126.     }
  127.  
  128. public:
  129.     void Solve(const vector<unsigned long> &a) {
  130.         t.total = std::accumulate(a.begin(), a.end(), (unsigned long) 0);
  131.  
  132.         vector<int> f;
  133.         vector<int> s;
  134.  
  135.         Solve(a, 0, f, s, 0);
  136.  
  137.         PrintArray(a, t.first, true);
  138.         PrintArray(a, t.second, false);
  139.     }
  140. };
  141.  
  142. // Псевдополиномиальный алгоритм o(n*sum) где sum - сумма элементов массива
  143. // Строим матрицу M(x,y) - x максимальный индекс для построения портфеля акции ценой 'y'
  144. // используем динамику и запоминаем откуда мы пришли в текущую ячейку . Это нужно для
  145. // постоения результирующего набора
  146. struct SolvePseudoPolinomial {
  147.  
  148.     void Solve(const vector<unsigned long> &a) {
  149.         struct Cell {
  150.             bool Reachable = false;
  151.             int share = 0;
  152.             pair<int, int> prev = {-1, -1};
  153.         };
  154.  
  155.         int best_sum = std::numeric_limits<int>::max();
  156.         Cell best_cell;
  157.  
  158.         auto total = std::accumulate(a.begin(), a.end(), (unsigned long) 0);
  159.  
  160.         auto num = total + 1;
  161.  
  162.         vector<vector<Cell>> m(a.size(), vector<Cell>(num, Cell()));
  163.  
  164.         m[0][a[0]] = {true, 0, {-1, -1}};
  165.  
  166.         for (int share = 1; share < a.size(); ++share) {
  167.             for (int value = 0; value < num; ++value) {
  168.  
  169.                 if ((share > 0) && m[share - 1][value].Reachable) {
  170.                     m[share][value] = m[share - 1][value];
  171.                 }
  172.  
  173.                 if (value == a[share]) {
  174.                     m[share][value] = {true, share, {-1, -1}};
  175.                 }
  176.  
  177.                 if (value > a[share] && m[share - 1][value - a[share]].Reachable) {
  178.                     m[share][value] = {true, share, {share - 1, value - a[share]}};
  179.                 } else {
  180.                     continue;
  181.                 }
  182.  
  183.                 if (abs((int)(total - 2 * value)) < abs(int(total - 2 * best_sum))) {
  184.                     best_sum = value;
  185.                     best_cell = m[share][value];
  186.                 }
  187.             }
  188.         }
  189.  
  190.         auto i = best_sum;
  191.         Cell &cell = best_cell;
  192.  
  193.         vector<int> first;
  194.         vector<int> second;
  195.  
  196.         // reconstruct first array
  197.         while (true) {
  198.             first.push_back(cell.share);
  199.             i -= a[cell.share];
  200.             if (!i) {
  201.                 break;
  202.             }
  203.             cell = m[cell.prev.first][cell.prev.second];
  204.         }
  205.  
  206.         std::reverse(first.begin(), first.end());
  207.  
  208.         // reconstruct second
  209.         int j = 0;
  210.         for (int i = 0; i < a.size(); ++i) {
  211.             if (i != first[j]) {
  212.                 second.push_back(i);
  213.             } else {
  214.                 ++j;
  215.             }
  216.         }
  217.  
  218.         PrintArray(a, first, true);
  219.         PrintArray(a, second, false);
  220.  
  221.     }
  222. };
  223.  
  224. int main() {
  225.     {
  226.         cout << "######################## Test 1 #########################" << endl;
  227.         vector<unsigned long> a {1, 2, 3, 3};
  228.         SolveBruteIterative().Solve(a);
  229.         cout << endl;
  230.         SolveBruteRecursive().Solve(a);
  231.         cout << endl;
  232.         SolvePseudoPolinomial().Solve(a);
  233.         cout << endl;
  234.     }
  235.  
  236.     {
  237.         cout << "######################## Test 2 #########################" << endl;
  238.         vector<unsigned long> a {5, 5, 5, 5, 20};
  239.         SolveBruteIterative().Solve(a);
  240.         cout << endl;
  241.         SolveBruteRecursive().Solve(a);
  242.         cout << endl;
  243.         SolvePseudoPolinomial().Solve(a);
  244.         cout << endl;
  245.     }
  246.  
  247.     {
  248.         cout << "######################## Test 3 #########################" << endl;
  249.         vector<unsigned long> a {5, 1, 1, 9, 7, 3};
  250.         SolveBruteIterative().Solve(a);
  251.         cout << endl;
  252.         SolveBruteRecursive().Solve(a);
  253.         cout << endl;
  254.         SolvePseudoPolinomial().Solve(a);
  255.         cout << endl;
  256.     }
  257.  
  258.     {
  259.         cout << "######################## Test 4 #########################" << endl;
  260.         vector<unsigned long> a {10, 16, 82, 69, 69, 53, 13, 12, 96, 23};
  261.         SolveBruteIterative().Solve(a);
  262.         cout << endl;
  263.         SolveBruteRecursive().Solve(a);
  264.         cout << endl;
  265.         SolvePseudoPolinomial().Solve(a);
  266.         cout << endl;
  267.     }
  268.  
  269.     {
  270.         cout << "######################## Test 5 #########################" << endl;
  271.         vector<unsigned long> a {19, 17, 13, 9, 6};
  272.         SolveBruteIterative().Solve(a);
  273.         cout << endl;
  274.         SolveBruteRecursive().Solve(a);
  275.         cout << endl;
  276.         SolvePseudoPolinomial().Solve(a);
  277.         cout << endl;
  278.     }
  279.  
  280.  
  281.     return 0;
  282. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin 
Standard input is empty
stdout 
######################## Test 1 #########################
FirstShares: [1,3,] FirstTotalValue: 4
SecondShares: [2,3,] SecondTotalValue: 5

FirstShares: [2,3,] FirstTotalValue: 5
SecondShares: [1,3,] SecondTotalValue: 4

FirstShares: [1,3,] FirstTotalValue: 4
SecondShares: [2,3,] SecondTotalValue: 5

######################## Test 2 #########################
FirstShares: [5,5,5,5,] FirstTotalValue: 20
SecondShares: [20,] SecondTotalValue: 20

FirstShares: [20,] FirstTotalValue: 20
SecondShares: [5,5,5,5,] SecondTotalValue: 20

FirstShares: [5,5,5,5,] FirstTotalValue: 20
SecondShares: [20,] SecondTotalValue: 20

######################## Test 3 #########################
FirstShares: [5,1,7,] FirstTotalValue: 13
SecondShares: [1,9,3,] SecondTotalValue: 13

FirstShares: [1,9,3,] FirstTotalValue: 13
SecondShares: [5,1,7,] SecondTotalValue: 13

FirstShares: [5,1,7,] FirstTotalValue: 13
SecondShares: [1,9,3,] SecondTotalValue: 13

######################## Test 4 #########################
FirstShares: [82,69,69,] FirstTotalValue: 220
SecondShares: [10,16,53,13,12,96,23,] SecondTotalValue: 223

FirstShares: [82,69,69,] FirstTotalValue: 220
SecondShares: [10,16,53,13,12,96,23,] SecondTotalValue: 223

FirstShares: [82,69,69,] FirstTotalValue: 220
SecondShares: [10,16,53,13,12,96,23,] SecondTotalValue: 223

######################## Test 5 #########################
FirstShares: [19,13,] FirstTotalValue: 32
SecondShares: [17,9,6,] SecondTotalValue: 32

FirstShares: [17,9,6,] FirstTotalValue: 32
SecondShares: [19,13,] SecondTotalValue: 32

FirstShares: [19,13,] FirstTotalValue: 32
SecondShares: [17,9,6,] SecondTotalValue: 32
https://ideone.com/DbUpGG
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!