6.状态压缩dp

动态规划算法的过程是随着阶段的增长，在每个状态维度上的分界点组成了DP拓展的轮廓。对于某些问题，我们需要在动态规划的状态中记录一个集合，保存这个轮廓的详细信息，以便于进行状态转移。若集合大小不超过 N NN ，集合中每个元素都是小于 k kk 的自然数，则我们可以把这个集合看做一个 N NN 位 k kk 进制数，以一个 [ 0 , k N − 1 ] [0,k^N-1][0,k N −1] 之间的十进制整数的形式作为DP状态的一维。这种把集合转化为整数记录在DP状态中的一类算法被称之为状态压缩动态规划算法。

在讲状压dp之前，我们应该清楚dp是解决多阶段决策最优化问题的一种思想方法，即利用各个阶段之间的关系，逐个求解，最终求得全局最优解。

我们通常需要确认原问题与子问题、动态规划状态、边界状态、状态转移方程。

动态规划多阶段一个重要的特性就是无后效性，即“未来与过去无关”。无后效性就是对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的发展。换句话说，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。

对于动态规划，如何定义状态是至关重要的，因为状态决定了阶段的划分，阶段的划分保证了无后效性。

状态压缩DP介绍

状态压缩DP其实是一种暴力的算法，因为它需要遍历每个状态，而每个状态是多个事件的集合，也就是以集合为状态，一个集合就是一个状态。集合问题一般是指数复杂度的NP问题，所以状态压缩DP的复杂度仍然是指数的，只能用于小规模问题的求解。

为了方便地同时表示一个状态的多个事件，状态一般用二进制数来表示。一个数就能表示一个状态，通常一个状态数据就是一个一串0和1组成的二进制数，每一位二进制数只有两种状态，比如说硬币的正反两面，10枚硬币的结果就可以用10位二进制数完全表示出来，每一个10位二进制数就表示了其中一种结果。

使用二进制数表示状态不仅缩小了数据存储空间，还能利用二进制数的位运算很方便地进行状态转移。

下面列举了一些常见的二进制位的变换操作。

例题讲解

给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。另给你一个整数 k 表示等待分发零食包的孩子数量，所有 零食包都需要分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。

分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最大总数。

返回所有分发的最小不公平程度。

提示：

• 2 <= cookies.length <= 8
• 1 <= cookies[i] <= 105
• 2 <= k <= cookies.length

题意理解

将n包具有一定饼干数量的零食分给k位小朋友，为了让能拿到最多饼干的小朋友拿到尽可能少的饼干，可理解为缩小贫富差距，求所有可行的零食分发方案中最多饼干那位小朋友最少的一种，为多少。

算法分析

如果你想先想出一套可行的零食分发算法再按部就班计算出答案，比如说使用贪心算法等，可能一辈子都解不出这道题来，因为这是一个NP类问题，即是一个可以在多项式时间内验证解的问题而目前无法在多项式时间内求出解的问题。

既然我们无法给出快速求取精确解的算法，但是可以穷举所有可行解，根据题目需要选取最优解。

由于问题规模较小，我们使用穷举法枚举每一种可能结果。

对于每一种可能结果，n 包零食的分发状态需要明确，这里使用n位二进制数j来表示，共有（1 << n）种可能。

对于已经分好零食的当前 k 位小朋友，设此时 n 包零食状态为j，比方说第 k 位小朋友拿到了其中的 2 包零食，设零食状态为c，那么对于当前 k 位朋友分好零食得到的结果，等价于，已经将前 k 位小朋友分好零食，再将那 2 包零食分给第 k 位小朋友后得到的结果。也就是说，分好 k 位朋友可由分好前 k 位朋友经过决策转移而来。

对于最优的决策，我们需要比较所有可能的决策来确定，设第 k 位朋友得到的零食状态c，这里使用技巧for(int c=j;c;c=(c-1)&j)枚举所有可能决策。

对于分好前 k 位朋友的零食状态，我们可以使用位运算轻松表示为j ^ c。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        int n=cookies.size();
        vector<int>s(1<<n); // 表示所有的零食包分发状态的不公平程度
        for(int i=0;i<n;i++){ 
            for(int j=0,c=(1<<i);j<c;j++){ // 将第i个零食包分发到所有子集
                s[j|c]=s[j]+cookies[i];
            }
        }
        vector<vector<int>>f(k,vector<int>(1<<n,INT_MAX)); // f[i][j]表示以零食包分发状态j时分给i个小朋友的最优解
        for(int i=0;i<(1<<n);i++){ // 分给一个小朋友时就是零食包分发状态的不公平程度
            f[0][i]=s[i];
        }
        for(int i=1;i<k;i++){
            for(int j=1;j<(1<<n);j++){
                for(int c=j;c;c=(c-1)&j){ // 将零食包分发状态j分给第i位小朋友
                    f[i][j]=min(f[i][j],max(f[i-1][j^c],s[c]));
                }
            }
        }
        return f[k-1][(1<<n)-1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <bits/stdc++.h>
using namespace std;
const int maxn = 21;
int f[1 << maxn][maxn];
int n, m, s, t, k, ans;
int w[maxn << 1][maxn << 1];
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++ i) 
        for (int j = 0; j < n; ++ j) 
            scanf("%d", &w[i][j]);
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i <= (1 << n) - 1; ++ i) {
        for (int j = 0; j < n; ++ j) {
            if ((i >> j) & 1) {
                for (int k = 0; k < n; ++ k) {
                    int now = i ^ (1 << j);
                    if ((now >> k) & 1)
                        f[i][j] = min(f[i][j], f[now][k] + w[k][j]);
                }
            }
        }
    }
    cout << f[(1 << n) - 1][n - 1] << '\n';
    return 0;
}

请我一杯咖啡吧！

赞赏

微信打赏