• 本文为作者的动态规划学习的历程，部分内容选自公众号labuladong，部分来自洛谷刷题时或者是平常作业中遇到的问题，进而在csdn的优质文章中学习或者是洛谷的题解中学习。文中各种dp并不按照广义的学习路线设置，属于作者自身的一个学习过程

四维dp问题

动态规划问题通常为一维或者二维，很少出现四维。

对于四维dp，有如下几个特点，

  • dp范围非常小，通常在10~50左右，保证在O(n4n^4)时间内能够解决。
  • 无法拆分成为两个二维，第一个二维能取到最优解，但是在此前提下，第二个二维dp只能取到局部最优，两者的和并不一定是全局最优解。
  • 根据题目信息可以归纳出四维之间的特殊关系

下面举两个例子来进行说明

  1. 洛谷p1004

题目要求在n*n的方格中从左上角取到左下角取两次，计算两次取数的最大结果

分析：定义dp[i][j][k][p]为第一次到达ij，第二次到达kp位置时的总数值，对于每一个点，只能从其左侧一格或者上侧一格到达。对于两次取数的两种状态，一共有四种综合转移情况

因此我们可以考虑状态转移方程

dp[i][j][k][p]=max(dp[i−1][j][k−1][p],dp[i−1][j][k][p−1],dp[i][j−1][k−1][p],dp[i][j−1][k][p−1])+map[k][p]dp[i][j][k][p]=max(dp[i-1][j][k-1][p],dp[i-1][j][k][p-1],dp[i][j-1][k-1][p],dp[i][j-1][k][p-1])+map[k][p]

我们来分析这个方程，四种位置变化的组合，最后加上对于转移到(k,p)点的数值map[k][p]

也许你会有疑惑为什么不加上转移到(i,j)点的数值map[i][j]; 别急，听我慢慢解释

两次移动虽然用一个方程表示，但是实质上是两次取数的过程，第一个人从左上到右下取完之后才进行第二个人取数（第一个人取过的位置都会变成0，但是对于我们的dp过程，我们不方便将map[][]的某一个位置的数值变成0）

但是不论如何取数，即使两个人的位置有重合，对于重合点的数值map[][],我们都可以都只加一次，也就是加上map[k][p],而对于map[i][j],我们将讨论相关条件来决定是否加入。

对于状态转移之后，也就是dp[i][j][k][p]点，表示已经到达这个状态的最大数值，那么到达此状态之后，我们可以将次状态分为两种情况

  1. 点(i,j)和(k,p)重合，那么意味着我们只用将这个点的数值计算一次，也就是map[k][p],不用考虑map[i][j]；
  2. 点(i,j)和(k,p)不重合，对于点(k,p)我们计算了其数值map[k][p],那么对于到达点(i,j)的数值map[i][j]没有计算，那么我们只需要加上map[i][j]即可；

到此状态转移方程分析结束，代码如下

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
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <stdlib.h>

int map[11][11];
int dp[11][11][11][11];

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    int n;
    scanf("%d", &n);
    while (1) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if (x == 0 && y == 0 && z == 0)break;
        map[x][y] = z;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                for (int p = 1; p <= n; p++) {
                    dp[i][j][k][p] = max(dp[i][j][k][p], dp[i - 1][j][k - 1][p] + map[k][p]);
                    dp[i][j][k][p] = max(dp[i][j][k][p], dp[i - 1][j][k][p - 1] + map[k][p]);
                    dp[i][j][k][p] = max(dp[i][j][k][p], dp[i][j - 1][k - 1][p] + map[k][p]);
                    dp[i][j][k][p] = max(dp[i][j][k][p], dp[i][j - 1][k][p - 1] + map[k][p]);
                    if (i != k || j != p)dp[i][j][k][p] += map[i][j];
                }
            }
        }
    }
    printf("%d", dp[n][n][n][n]);
    return 0;
}
  1. 洛谷p1006

这道题和上面的方格取数有很大的相似处，但是也有部分不同，两个人的路径无法交叉,矩阵大小m行n列

分析：路径无法交叉，意味着从左上角的同一点出发时就只能一个人向下并且到达右下顶点的左侧，一个人向右迈出第一步并且到达右下顶点的上侧；

这里是对于起始点和终点的判定防止交叉; 这里我们假定开始向下的为第一个人，向右的是第二个人

同理我们定义dp[i][j][k][p]表示第一个人到达[i][j]，第二个人到达[k][p]位置时的数值（好感度）总和

考虑第一个人，他能涉及的区域应该为矩形左上角(1,1),右下角(m,n-1)，因此外层循环如下

1
2
3
4
5
for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n-1; j++) {
            //balabala
        }
}

虽然状态转移考虑的时候我们考虑两个人同时进行位置改变，但是实质上是第一个人到达(i,j)，在此前提之下，因为事实情况是第一个人已经到达这个确定的位置（这个位置已经是合法的了），那么说明第二个人的路径没有和第一个人当前的路径有重合，我们再来考虑第二个人，因为不能有路径交叉，第一个人的考虑范围为矩形左上角(1,j+1)，右下角(m-1,n);

因为这个(i,j)能涉及的范围包括整个矩形(1,1),(i,j);所以让p>j即可保证无重合;状态转移方程如下

dp[i][j][k][p]=max(dp[i−1][j][k−1][p],dp[i−1][j][k][p−1],dp[i][j−1][k−1][p],dp[i][j−1][k][p−1])+map[k][p]+map[i][j]dp[i][j][k][p]=max(dp[i-1][j][k-1][p],dp[i-1][j][k][p-1],dp[i][j-1][k-1][p],dp[i][j-1][k][p-1])+map[k][p]+map[i][j]

整体代码如下

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
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <stdlib.h>

int map[53][53];
int dp[52][52][52][52];

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m;
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n - 1; j++) {
            for (int k = 1; k <= m - 1; k++) {
                for (int p = 1 + j; p <= n; p++) {
                    dp[i][j][k][p] = max(dp[i][j][k][p], dp[i - 1][j][k - 1][p] + map[k][p] + map[i][j]);
                    dp[i][j][k][p] = max(dp[i][j][k][p], dp[i - 1][j][k][p - 1] + map[k][p] + map[i][j]);
                    dp[i][j][k][p] = max(dp[i][j][k][p], dp[i][j - 1][k - 1][p] + map[k][p] + map[i][j]);
                    dp[i][j][k][p] = max(dp[i][j][k][p], dp[i][j - 1][k][p - 1] + map[k][p] + map[i][j]);
                }
            }
        }
    }
    printf("%d", dp[m][n - 1][m - 1][n]);
    return 0;
}

这里是四维，但是仔细想一下，从左上角到右下角，因为两人路径互不干扰，因此可以假设两人同时进行，步数一样

那么可以得到方程 i+j=p+q,因此只需要枚举三个坐标i，j，k即可得到第四个坐标q（q从j+1开始），降低阶数到3阶；

背包问题

01背包

​ 有n件物品，每一件物品有对应的价值value和重量weight，有背包最大容量max，如何选取物品，在不超过背包容量的情况下取得最大的总价值

​ 分析：我们可以定义dp[i][j]为考虑前i件物品，背包容量为j，能装下的最大价值

​ 在前i-1件物品考虑完的情况下，我们考虑第i件物品，对应的value[i]和weight[i],

  • 如果背包此时的j<weight[i]，那么无法装下第i件物品，那么考虑前i件物品和考虑前i-1件物品的价值是一样的，状态转移方程为：

dp[i][j]=dp[i−1][j]dp[i][j]=dp[i-1][j]

  • 如果背包装得下，也就是j>weight[i]，那么此时有两种取向，装第i件商品和不装第i件商品，取两者的最大值，状态转移方程为：

dp[i][j]=max(dp[i][j],dp[i−1][j−weight[i]]+value[i])dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i])

因此代码如下

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
30
31
32
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#define max_num 100
#define max_weight 200
int weight[202], value[202];
int dp[max_num][max_weight];//dp[i][j]表示考虑前i件商品，有j的容量能取到的最大价值 
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m;//m就是定义的最大容量 
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j < weight[i])dp[i][j] = dp[i - 1][j];
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    printf("%d", dp[n][m]);
    return 0;
}

优化：滚动数组（后面有时间再写详细优化解释）

1
2
3
4
5
6
int dp[max_weight];
for (int i = 1; i <= n; i++) {
	for (int j = m; j >= weight[i]; j--) {
		dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
	}
}

多重背包

​ 对于n件商品，每一件对应有价值value和weight，每一件商品有num件，对于容量为max的背包，如何选取商品获得最大价值

​ 分析：将每一件商品的num件都进行拆解，转换成数据量更大的01背包问题，问题在于，数据量更大可能超时，因此需要进行优化

​ 考虑这样一个问题，对于一种商品的num件，我们可以选取任意件，但是有没有更好的方法表示这任意件商品呢？

​ 这里我们讨论关于二进制优化，给你一个数字k，你可以将其表示成为

​ k=1+2+4+8+16+......+2m+tk=1+2+4+8+16+......+2^m+t;这里的m取最大值，然后剩余一个数字t，举个例子：

  • 27=1+2+4+8+12；
  • 49=1+2+4+8+16+17；
  • 235=1+2+4+8+16+32+64+108；

这样有什么用呢？ 对于数字27，原来数字15=1*15（需要15个1来表示15），现在可以压缩成15=1+2+12； 11=1+2+8；

也就是对于数字的分解k=1+2+4+8+16+......+2m+tk=1+2+4+8+16+......+2^m+t，对于任意小于等于k的数字q，q可以用k的分解数字组合而成，从而进行压缩

这样我们也可以对num件同样的物品进行二进制压缩，把每个压缩的数字作为一个整体的新的物品

代码如下：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#define max_num 100
#define max_weight 200
int weight[202], value[202];
int dp[max_num][max_weight];

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m;
    int v, w, num;
    int cnt = 1;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &v, &w, &num);
        //对num进行2进制拆解，1，2，4，8，16 .........以及一个无法继续取到的余数
        int k = 1;
        while (k <= num) {
            value[cnt] = v * k;
            weight[cnt++] = w * k;
            num -= k;
            k <<= 1;//k乘以2
        }
        if (num > 0) {
            value[cnt] = v * num;
            weight[cnt++] = w * num;
        }
    }//那么就是前cnt件商品
    for (int i = 1; i <= cnt - 1; i++) {
        for (int j = 0; j <= m; j++) {
            if (j < weight[i])dp[i][j] = dp[i - 1][j];
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    printf("%d", dp[cnt][m]);
    return 0;
}

分组背包

一共有m组物品，每一组物品对应有s[i]个，对应每个物体有value和weight；背包容量为max，每一组物品中最多只能选择一个，如何选取获得最大的价值

分析：与01背包的差别在于，每一组的个数更多了，因此原来的考虑第i个物品，变成了考虑第i组物品

我们依然定义dp[i][j]为前i组物品，j容量对应的最大价值。

我们来考虑第i组物品，一共有s[i]个，假设不取i组的物品

dp[i][j]=dp[i−1][j];dp[i][j]=dp[i-1][j];

然后再依次考虑第i组所有物品对应的情况，遍历该组的每一个物品，考虑其取与不取对应的最大价值

当然需要前提判断，当前容量j能够放下我们考虑的物品，if(j>=s[i][k]),第i组的第k个物品

dp[i][j]=max(dp[i][j],dp[i−1][j−weight[i][k]]+value[i][k])dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i][k]]+value[i][k])

因此代码如下

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
30
31
32
33
34
35
36
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#define max_num 100
#define max_weight 200
int weight[100][max_weight], value[100][max_num];
int s[100];//表示每一组有多少个物品
int dp[100][max_weight];//前i组，最大价值 
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);//有很多个组，每个组最多只能选择一个物品 
        for (int j = 1; j <= s[i]; j++) {
            scanf("%d%d", &value[i][j], &weight[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];//不选第i组，从前i-1组里面选择
            for (int k = 1; k <= s[i]; k++) {//遍历第i组的所有物品 
                if (j >= weight[i][k])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i][k]] + value[i][k]);
            }
        }
    }
    printf("%d", dp[n][m]);
    return 0;
}

完全背包

一共有n种物品，每个物品有无限个，对应有value和weight，背包容量为max，求解取到的最大价值

分析：如果我们把每一种物品的无限数量进行拆分，依然是01背包问题，或者是多重背包问题（只是这里无上限，不好进行优化），我们只需要在01背包基础上枚举每一种物品取的数量k即可，代码如下

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#define max_num 100
#define max_weight 200
int weight[202], value[202];
int dp[100][200];

int max(int a, int b) {
    return a > b ? a : b;
}
//这里看作01背包
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= max_weight; j++) {
            for (int k = 0; k * weight[i] <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weight[i]] + k * value[i]);
            }//去遍历对于每件商品的所有取值情况，取最大的价值的情况作为结果
        }
    }
    return 0;
}

接下来我们仔细分析这段代码，显然发现

dp[i][j]=max(dp[i−1][j],dp[i−1][j−k∗weight[i]]+k∗value[i])...k=1,2,3,4dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*weight[i]]+k*value[i])... k=1,2,3,4

我们将j替换成j-weight[i]有

dp[i][j−weight[i]]=max(dp[i−1][j−weight[i]],dp[i−1][j−k∗weight[i]]+k∗value[i])...k=2,3,4,5,6dp[i][j-weight[i]]=max(dp[i-1][j-weight[i]],dp[i-1][j-k*weight[i]]+k*value[i])...k=2,3,4,5,6

观察两个式子，我们发现两个式子可以把k给抵消掉（采用递归的形式消去k）（递归的过程是j从小到大递归，因此在代码的循环部分j也要从小到大），两个式子整合为下面式子 （读者可以自己多列举几个k的数值去理解这里是如何整合的）

dp[i][j]=max(dp[i−1][j],dp[i][j−weight[i]]+value[i])dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i])

因此代码在时间复杂度上可以优化成这样（三维到二维）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define max_weight 200
int weight[202], value[202];
int dp[100][200];

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j < weight[i])dp[i][j] = dp[i - 1][j];
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
            }
        }
    }
    printf("%d", dp[n][m]);
    return 0;
}

背包问题总结

四种背包问题在本质上都可以解释为01背包问题，简单的二维dp，只是附加了不同的条件，需要对应不同的方法去优化加强版的01背包，这些优化都是基于时间上的优化，但是背包问题普遍都可以使用滚动数组优化空间到一维。滚动数组优化以及各种背包问题的循环嵌套顺序，遍历顺序（从小到大或者是从大到小），可以自己尝试画出二维的递归表格，通过填涂表格的形式更好的理解嵌套和遍历顺序。

当然，嵌套和遍历顺序我们也可以通过状态转移方程推出，背包问题属于最基础形式的动态规划问题。