Advertisement
ismaeil

Algo 1

Aug 10th, 2020
618
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.78 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define OO INT_MAX
  4.  
  5. const int N = 1e2 + 2e1;
  6. int optA = 0 ,optB = OO;
  7. bool cur[N] ,opt[N];
  8. int n ,A[N];
  9.  
  10. void BT(int i ,int sumA ,int sumB){
  11.     if( i > n ){
  12.         if( abs(sumA - sumB ) < abs(optA - optB)){
  13.             optA = sumA;
  14.             optB = sumB;
  15.             for(int i=1 ; i<=n ; i++) opt[i] = cur[i];
  16.         }
  17.         return;
  18.     }
  19.  
  20.     cur[i] = 0;
  21.     BT(i+1 , sumA , sumB + A[i] );
  22.  
  23.     cur[i] = 1;
  24.     BT(i+1 , sumA + A[i] , sumB);
  25.     cur[i] = 0;
  26. }
  27.  
  28. int main() {
  29.     cin >> n;
  30.     for(int i=1 ; i <= n ; i++)
  31.         cin >> A[i];
  32.  
  33.     BT( 1 , 0 , 0 );
  34.  
  35.     cout << optA << ' ' << optB << endl;
  36.     for(int i = 1 ; i <= n ; i++)
  37.         cout << opt[i] << ' ';
  38.     cout << endl;
  39.     return 0;
  40. }
  41.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement