状态压缩动态规划【状压DP】模板+例题

例题一。

n个人在做传递物品的游戏，编号为1~n。

游戏规则是这样的，开始时物品可以在任意一人手上，他可以把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。

即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值没有联系。

求当物品经过所有n个人之后，整个过程的总代价最小是多少？

【解析】

我们可以将"当前传递过物品的人的集合,最后一个传递到得人"作为 状态 进行动态规划，用dp[i][j]表示这个状态的最小代价。

这里，我们就要用到状态压缩，把“传递过物品的人的集合”压缩为一个整数，我们用二进制表示这个集合，比如一共5个人，第0、3、4个人被传递过（为了方便起见，序号从0开始），就用11001(2进制)表示，该集合的十进制表示为25。

注意到j是最后一个被传递到的人，也就是说必须在传递集合i中标记为1，即合法状态必须满足(i&(1<<j)) != 0。也即(i&(1<<j))为true。如果从j传递到k，那k必须不再集合i里。即必须满足(i&(1<<k))==0。

转移方程为dp[i|1<<k][k] = min(dp[i|1<<k][k], dp[i][j] + a[j][k]。其中a[j][k]为从j传递到k的代价。

因为开始时物品的可以在任意一人手上，所以把dp[1<<i][i]置为0，其他状态置为无穷大。

总的时间复杂度为O(n^2 * 2^n).

【Note】

• 一个集合s，怎么把第j个人加进来?即s或上(1左移j位)。也即“s|(1<<j)"即可。
• 判断第j个人是否在集合i中？即i&(1<<j)，如果为true则存在，否则不存在。

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
int n;
int a[20][20];
int dp[1<<16][20];//dp[i][j]表示“当前传递过物品的人的集合,最后一个传递到的人"状态下的最小价值.

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n; i++) {
        dp[1<<i][i] = 0;
    }
    for (int i = 0; i < (1<<n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1<<j)) {
                for (int k = 0; k < n; k++) {
                    if (!(i & (1<<k))) {
                        dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k], dp[i][j] + a[j][k]);
                    }
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[(1<<n) - 1][i]);
    }
    cout << ans << endl;
    return 0;
}
/*
Input:
3
-1 2 4
3 -1 5
4 4 -1

Output:
6
*/