突然翻到自己以前给老师写的一篇SA的简单讲解，晒在这里（悲），看看以前的自己

/*
题目：
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，
每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。

有基础的同学一看到这题目第一想到的应该就是dp之01背包问题，那如果数据大一点，dp会TLE怎么办呢
————那当然是用十分玄学的模拟退火SA算法（属于启发式搜索，时间复杂度低的可怕，甚至可以用一些奇奇怪怪的函数卡评测机，
但解不一定最优，这时候就考验个人的调参能力了）

以下为百度给的解释：
模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，
加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
说白了就是把热力学的东西扔到概率学里
详情见以下代码
*/
#include <bits/stdc++.h>
#define inline __attribute__ ((always_inline))//强制内联，此处用不到，不用管
using namespace std;
vector<int>v;//物品重量
vector<bool>vis;//物品是否被选中
double T=1e5,min_T=1e-6,alpha=0.995;//T：当前温度；min_T：终止温度；alpha：降温速度
int steps=3000;//每个温度时迭代次数
int best_v,best_ans;//best_v：历史最优总重量；best_ans：最优解，与最优能量合并在一起
signed main(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //上面三行为读写优化，数据大时很有用
    int V,n;
    cin>>V>>n;
    default_random_engine rd(time(NULL));
    uniform_int_distribution<int> dis(1,n);
    uniform_real_distribution<double> dis2(0.0,1.0);
    //此处为“均匀”在范围内选取随机数，第一行为种子，第二行属于整数类随机数（中间int非指为int类型），第三行为浮点类随机数
    //备注：整数类范围为[],浮点类为[)
    v.resize(n+1);
    vis.resize(n+1);
    best_ans=V;
    for(int i=1;i<=n;i++)
        cin>>v[i],vis[i]=0;
    //初始化及数据读入
    //一下为SA主体部分
    while(T>min_T){
        for(int i=1;i<=steps;i++){
            int cur=dis(rd);
            bool is_sel=vis[cur];
            //随机选取区间内任一物品，并做操作
            int cur_v=(is_sel?-v[cur]:v[cur])+best_v;
            //计算当前总重
            int cur_en;
            if(cur_v>V)cur_en=(cur_v-V)*1000000;
            //若当前重量超过极限重量（非法），则对其施加极高的惩罚值
            else cur_en=V-cur_v;
            //否则正常计算
            int delta=cur_en-best_ans;
            if(delta<0||dis2(rd)<exp(-delta/T)){
                //!!!!!此处便是与爬山法不同的地方，运用Metropolis准则，以一定概率接受即使非法的解(避免陷入局部最优解)
                best_v=cur_v;
                vis[cur]=!is_sel;
                if(cur_v<=V&&(V-cur_v)<best_ans){
                    //若重量合法且更优，则更新当前答案
                    best_ans=V-cur_v;
                    if(best_ans==0){//小优化，若已经最优（剩下0）直接退出；
                        cout<<0;
                        exit(0);
                    }
                }
            }
        }
        T*=alpha;//降温
    }
    cout<<best_ans;
    return 0;
}