daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Jun 19th, 2017 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. using namespace std;
  3.  
  4. void sets(int& min, int i, int n, int grupo0, int grupo1, int& boundGrupo0, int boundGrupo1, const vector<int>& v) {
  5.     if(grupo0 > boundGrupo0 || grupo1 > boundGrupo1) {
  6.         return;
  7.     }
  8.     if (i == n) {
  9.         if(grupo0 >= grupo1) {
  10.             boundGrupo0 = grupo0;
  11.             if(grupo0-grupo1 < min) {
  12.                 min = grupo0-grupo1;
  13.             }
  14.         }
  15.     } else {
  16.         sets(min, i+1, n, grupo0+v[i], grupo1, boundGrupo0, boundGrupo1, v);
  17.         sets(min, i+1, n, grupo0, grupo1+v[i], boundGrupo0, boundGrupo1, v);
  18.     }
  19. }
  20.  
  21. int main() {
  22.     int n;
  23.     while(cin >> n) {
  24.         vector<int> v(n);
  25.         int max = 0;
  26.         for(int i = 0; i < n; ++i) {
  27.             cin >> v[i];
  28.             max += v[i];
  29.         }
  30.         int min = max;
  31.         int boundGrupo0 = max;
  32.         sets(min, 0, n, 0, 0, boundGrupo0, max/2, v);
  33.         cout << min << endl;
  34.     }
  35.  }
RAW Paste Data
Top