paradox64ce

Bitmask

Jun 19th, 2021
690
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bool check(int k, int N, int W, vector<int> w){
  2.     // multiset<int> st;
  3.     // for(auto x:w){
  4.     //     st.insert(x);
  5.     // }  
  6.    
  7.     vector<int> boxes(k, W);
  8.     vector<int> taken(N, false);
  9.    
  10.     int box = 0;
  11.    
  12.     while(box<k){
  13.         bool flag = 0;
  14.         bool flag2 = 1;
  15.         int max_sum = 0, power=0;
  16.         for(int i = 0;i<(1<<N);i++){
  17.             int sum = 0;
  18.             for(int j = 0;j<N;j++){
  19.                 if(((i>>j) & 1) && !taken[j]){
  20.                     sum+=w[j];
  21.                 }
  22.                 if(sum> max_sum && sum<=boxes[box]){
  23.                     max_sum = max(sum, max_sum);
  24.                     power = i;
  25.                     flag = true;
  26.                 }
  27.             }
  28.         }
  29.        
  30.        
  31.         boxes[box]-=max_sum;
  32.        
  33.         for(int j=0;j<N;j++){
  34.             if(((power>>j) & 1) && !taken[j]){
  35.                 taken[j] = 1;
  36.             }
  37.         }
  38.        
  39.        
  40.         if(!flag){
  41.             box++;
  42.         }
  43.        
  44.         for(int i = 0;i<N;i++){
  45.             if(!taken[i]){
  46.             flag2 = false;
  47.         }
  48.            
  49.         if(flag2){
  50.             break;
  51.         }
  52.     }
  53.        
  54.     }
  55.    
  56.     for(int i = 0;i<N;i++){
  57.         if(!taken[i]){
  58.             return false;
  59.         }
  60.     }
  61.    
  62.     return true;
  63. }
  64.  
  65. int get_minimum_parcels(int N, int W, vector<int> w) {
  66.     // Write your code here. Complete this function to return the minimum number of parcels required by Michael.
  67.     sort(w.begin(), w.end());
  68.    
  69.     int l = 1, r = N, ans = N;
  70.     while(l<=r){
  71.         int m = (l+r)/2;
  72.         if(check(m, N, W, w)){
  73.             ans = m;
  74.             r = m - 1;
  75.         }else{
  76.             l = m + 1;
  77.         }
  78.     }
  79.     return ans;
  80. }
RAW Paste Data