模拟退火算法

eg1:
Leecode

class Solution {
public:
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        w = groups;
        n = w.size();
        m = batchSize;
        ans = 0;
        for(int i = 0; i < 80; i++) simulate_anneal();
        return ans;
    }

private:
    int n, m;
    vector<int> w;
    int ans;

    int calc() {
        int res = 1;
        for(int i = 0, s = 0; i < n; i++) {
            s = (s + w[i]) % m;
            if(!s && i < n - 1) res++;
        }
        ans = max(ans, res);
        return res;
    }

    void simulate_anneal() {
        random_shuffle(w.begin(), w.end());
        for(double t = 1e6; t > 1e-5; t *= 0.97) {
            int a = rand() % n, b = rand() % n;
            int x = calc();
            swap(w[a], w[b]);
            int y = calc();
            int delta = x - y;
            if(!(exp(-delta / t) > (double)rand() / RAND_MAX)) {
                swap(w[a], w[b]);
            }
        }
    }
};

eg2:
Leecode

class Solution {
public:
    
    //通过预处理，快速求解arr[L..R]的与值
    int pre[100001][20] = {0};
    
    int get(int L, int R, int target) {
        int val = 0;
        for(int i = 0, bit = 1; i < 20; i++, bit <<= 1) {
            // 如果第 i 个bit 在 [L,R] 中全为 1，那么与值的该bit也必然为 1。
            if(pre[R][i] - pre[L-1][i] == R-L+1) {
                val |= bit;   
            }
        }
        return abs(val-target);
    }
    
    // 用模拟退火求解关于 L 的局部最优解
    int query(int L, int n, int target) {
        int dir[2] = {-1, 1};  // 两个方向
        int step = 1000; // 初始步长
        int now = L; // R 的起始位置
        int best = 100000000; // 局部最优解
        
        while(step > 0) {
            int Lpos = now + step*dir[0];
            if(Lpos < L) {
                Lpos = L;
            }
            int Rpos = now + step*dir[1];
            if(Rpos > n) {
                Rpos = n;
            }
            // 向左右两个方向各走一步，求值
            int ldis = get(L, Lpos, target);
            int rdis = get(L, Rpos, target);
            int pbest = best;
            
            //更新位置及最优解
            if(ldis < best) {
                now = Lpos;
                best = ldis;
            }
            if(rdis < best) {
                now = Rpos;
                best = rdis;
            }
            
            //如果没有找到更优解，那就缩小步长
            if(pbest == best) {
                step /= 2;
            }
        }
        return best;
    }
    
    int closestToTarget(vector<int>& arr, int target) {
        int anw = 100000000;
        
        //统计前 i 个数字中，第 j 个bit 为 1 的数量。
        for(int i = 0; i < arr.size(); i++) {
            for(int j = 0, bit = 1; j < 20; j++, bit <<= 1) {
                pre[i+1][j] = pre[i][j] + ((bit&arr[i]) ? 1 : 0);
            }
        }
        
        for(int i = 1; i <= arr.size(); i++) {
            anw = min(anw, query(i, arr.size(), target));
        }
        
        return anw;
    }
};