一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短？请输出最短行程。节点个数\(N\)满足\(2\leqN\leq20\)，路的长度小于\(1000\)。
我们知道，动态规划是根据之前已经计算好的状态推出后面一种状态，这道题亦是如此。也许有人会说，跑一遍最短路不就好了吗？但是最短路不保证走遍每一个点，而即使我们加上了点的计数，那也不能保证从\(A\)上不存在一个环（往回走的环），其节点个数恰好弥补了那些没扫过的节点。而且计数的时候还没到终点的点该如何更新呢？说不定一不小心就更没了，而且如果把每种情况都记录下来，是不亚于枚举的。但是仍有一些弱数据可以被水过去（NOIP），而且这种求最小值的状态压缩题甚至可以被一些优秀的随机化算法（模拟退火）等水过去。不过这些算法最怕的就是求所有状态的题目了，而状态压缩DP就做到了求出所有状态这一点。
由于博主水平有限，无法带领大家一步一步推理，因此我们就针对递推式进行讲解吧。其递推式为：
其中\(f[S][v]\)表示的是从\(v\)出发访问所有不属于集合\(S\)的顶点，最终回到\(0\)的路径的权重总和的最小值。而集合\(V\)表示为所有城市的集合，不难理解从\(0\)到\(0\)就是路程为\(0\)对吧，并且再将其它所有情况均赋值为无穷大（当然不可能是无穷大啊，找一个达不到的值即可），以防计算不存在的情况。其他的话，递推式已经表达得很明白了，大家也可以举几个例子帮助自己理解（注意，里面有些状态是对答案没用的，大家可以找一找，后面我会提到）。
注意这里出现了集合表示法，但是似乎不好怎么表示这个集合，难道用\(set\)表示吗？那就慢了！别忘了二进制这个好东西。
注意到我们的\(int\)可以表示到\(2^{31}-1\)，然而这里的\(N\)才这么大一点，那么我们就可以在二进制位中逐位保存某个点“存在”和“不存在”的情况。再者，这只需涉及到二进制的位运算，所以整体来说还是很快的。
那么我们现在来为一些稍缺知识的同学补充一些二进制表达集合的方法吧！
二进制表达想必学过一些二进制的人都知道吧，我们需要做的仅仅是摒弃它的十进制的模样（别影响了自己的理性思维）。假设现在有一个集合\(S=\emptyset\)，表示为二进制就是\(00000000\)（假装只有\(8\)位），然后我们往里面加入\(0\)，那么在二进制位的第\(0\)位就要改为\(1\)，也就是\(S=S\cup\{0\}=S\vee2^0=S|1<<0\)。同理，如果往里面加入\(6\)，就是\(S|=1<<6\)（此处计算机表示法均用C++表达）。
如果是判断\(u\)是否存在于集合\(S\)中的话，那么只需要判断\(S\vee2^u\)（即C++中的\(S\And(1< 注意，这道题十分卡常！仍然需要优化！但请一步一步看下来，不要急于求成！ 下面这段代码仅能得到\(80\)分，但是开\(O2\)可以险过。 #include 注意到\(min\)中的\(f[S\cup\{u\}][u]\)保证了\({u}\)必然在集合\(S\cup\{u\}\)里面，有人可能会说这是废话，但是这说明了在前面的状态中，\(v\)必然在集合\(S\)里面啊！因此对于\(v\)不在集合\(S\)中的情况就不必考虑了。但是，注意当\(S\)为空（程序中变为\(0\)）的时候它就不会继续走答案了，也就是说我们要特殊处理一下这种情况。 于是我们得到了\(90\)分代码。 #include 让我们再从头开始看，看那个递推式（稍改）。 最开始\(S\)二进制位（位数小于\(N\)）全部是\(1\)的时候，仅\(0\)号点为\(0\)，其它都是\(INF\)。而有些\(INF\)是可以推到底层的！那什么样的情况满足其\(f\)恒为\(INF\)呢？首先注意到\(f[V][x],x\neq0\)的情况恒为\(INF\)，那这个状态又会推到哪里呢？根据递推式： 我们有： 容易得到\(f[S][v]\)必然为\(INF\)（因为\(u\)只有一种可能）。 同理，对于递推式： 故对于任何满足\(\{0\}\inS\)的\(f[S][v]\)，它们的值恒为\(INF\)。用二进制表示法来说，只要\(S\And1\)为真，那么就无需考虑。 那么程序就可以“进化”了，从而拿到\(100\)分！ #include 注意：以上数据均在洛谷测试，均为C++语言。 在状态压缩DP里面，我们也经常会碰到一些“棋盘”题。如果直接暴力搜索的话，会产生“状态爆炸”的尴尬局面，于是我们就需要一个美妙的优化方案——轮廓线优化了。 题目大意：有一块\(M\timesN\)（\(1\leqM,N\leq12\)）的长方形牧场，分割的每一块土地都是正方形的（说白了就是棋盘），农夫要在某几格种上牧草或者干脆不种。要求是：不能种在贫瘠的土地上；各个土地上的牧草不能有公共边。土地状况会在输入中给出，求不同的种植方案的个数，答案对\(10^8取模\)。（看你们还怎么用模拟退火） 也许有人会说：啊！这还怎么用状态压缩啊！\(M\timesN\)早就爆炸了啊！（说好的冷静呢） 其实这题有人就这么过了，还写了题解，确实比别的好理解，不过代价就是太慢了。 额哼，不扯了，我们切入正题吧。 其实我们这里没必要搞出这么多状态，我们的方法其实就是逐行递推（逐行动态规划）。转移方程该怎么写呢？也不难，就是根据当前考虑的格子的左边和上面的状态得到当前格的状态。但是要注意不存在的情况及时过滤！于是我们得到递推式： 第一个赋值式表示的是初值（经验所得，下方有答疑）；第二个递推式表示的是这个点不被选取的情况；第三个递推式表示这个点被选取的情况。但是需要注意的是，如果这个点被选了，那么第二第三条递推式都要写上，因为农夫可以选择不种（别被细节坑了哦）！ 哦，对了，对于某格上面存在草的情况，递推下来的时候要递推到这格不种草的情况，图示： 不能种的情况： 但是仍然要转移过来，不然怎么递推到最后一行去统计呢？如果不清楚的话，下文会提到为什么要在最后一行统计。 您可能会问的问题： 为了追求完美，博主用了滚动数组（也就是数组重复利用，不浪费空间）。 下面是满满的注释的代码，博主满满的爱。 旧洛谷机子上面必然为0ms的代码，别问我为什么。因为新测评机没有0ms了啊！没赶上啊！不过在洛谷IDE（老测评机）测试全为可种草的土\(12\times12\)的数据中，跑出来是0ms的。 还有，这些状态压缩DP只是小部分，后续我可能还会继续更新，比如插头DP等。 请你将下列缺陷填好，使其成为完整的旅行商问题的程序： #include 推荐大家看看《挑战程序设计竞赛（第二版）》，讲的也很好噢~感谢参考文献中提到的文献的帮助。除参考部分外，大多数内容（如常数优化，较为通俗的理解，图片等）均为个人智力成果，如需转载，请注明出处，禁止作商业用途传播。最后，感谢各位的阅读。