二进制状态压缩，是指将一个长度为`m`的 bool 数组用一个长度为 m 的二进制整数表示并存储的方法。 利用下列位运算操作可以实现原 bool 数组中对应下标元素的存取。
操作运算取出整数 n 在二进制表示下的第 k 位n & (1 << k)取出整数 n 在二进制表示下的第 0 ~ k - 1 位（后 k 位）n & ((1 << k) - 1) 把整数 n 在二进制表示下的第 k 位取反n ^ (1 << k)对整数 n 在二进制表示下的第 k 位赋值1n | (1 << k)对整数 n 在二进制表示下的第 k 位赋值0 n & (~(1 << k))这种方法运算简便，并节省了程序运行的时间和空间。
例题 ： 最短 Hamilton 路径
给定一张 n(n <= 20) 个点的带权无向图，点从 0 ~ n - 1 标号， 求起点 0 到终点 n - 1的最短 Hamillton 路径。 Hamilton 路径的定义是从 0 到 n - 1 不重不漏的经过每一个点恰好一次。
如上图所示从1点出发，到终点5，不重不漏的经过所有点且代价最小的路径应该是 1 - 4 - 3 - 2 - 5 ， 代价为 6。
首先很容易想到暴力法，就是枚举 n 个点的全排列，计算路径长度取最小值， 时间复杂度为 O (n * n!)
我们使用一个 n 位的二进制数来表示哪些点已经被经过，那些点没有被经过。 如 11011 表示 0 ，1， 3， 4 点被经过 而 2 点没有被经过。 因此 我们可以使用 F[i, j] ( ) 表示 点被经过的状态对应的二进制数 i ，且目前处于点 j 时的最短路径。我们从起点出发，即有 F[1, 0] = 0 ， 即只经过了点 0， 目前起点处于 0， 最短路径长度为 0。为了方便起见，我们将 F 数组的其他值都设为无穷大。 最终目标是 F[(1 << N) - 1, n - 1]。
不难理解 状态转移过程即为 当前状态 = min {当前状态， 从其它点走到当前点的权重 + 前一个状态}
状态方程 ： F[i, j] = min{ F[i , j], F[i ^ (1 << j)][k] + weight[k][j] , F[i][j] }
同时需要满足两个条件：
1、((i >> j) & 1) == 1 即当前状态所在的位置必须是当前状态走过的位置
2、((i >> k) & 1) == 1 即上一个状态所在的位置必须是当前状态走过的状态
代码如下：
Class Hamilton{ public int himilton(int n, int[] weight){ int f[][] = new int[1 << n][n]; for(int i < 0; i < 1 << n; i++){ Arrays.fill(f[i], Integer.MAX_VALUE); } f[1][0] = 0; for(int i = 1; i < 1 << n; i++){ for(int j = 0; j < n; j++){ if(((i >> j) & 1) != 1) continue; for(int k = 0; k < n; k++){ if(((i >> k) & 1) != 1) continue; f[i][j] = Math.min(f[i][j], f[i ^ (1 << j)][k] + weight[k][j]); } } } return f[(1 << n) - 1][n - 1]; } }
