数据结构与算法模板总结(五)-动态规划(背包)

• 背包问题的dp思路

• 背包模型

• 0-1背包

• 完全背包

• 多重背包

• 分组背包

背包问题的dp思路

通常从两个角度来考虑DP问题：

1. 状态表示：

   首先考虑问题需要用几维的状态来表示，每个状态f(i,j)表示的是一个集合，f(i,j)存的是集合中所有选法的总价值的最大值。

   f(i,j)表示：「1.只从前i个物品中选」，「2.总体积<=j的选法集合」。存的数量是每个选法的总价值的最大值。

2. 状态计算：

   状态计算求算的是，如何一步步的把每个状态算出。f(N,V)是所有选法总价值的最大值，表示从所有N个商品中选，并且总体积不超过V的选法的集合。

   集合划分考虑把当前集合划分为若干个小的子集，使得每个子集可以用前面更小的状态表示出来。

注：f(i, j)存的是集合中所有选法的最大值，存的是一个数。

背包模型

背包模型可以描述为：有N个物品和一个容量为V的背包，每一个物品有两个属性：一个是体积，一个是价值。从中挑一些物品，使得总体积<=V，求挑出物品最大价值。根据限制的不同，背包问题可以分为四种情况：

1. 0-1背包：每个物品最多用一次；
2. 完全背包：每个物品有无限个；
3. 多重背包：每个物品最多有个，不同物品的值可能不同；
4. 分组背包问题：每组最多选一个物品；

0-1背包

题目

题目链接：https://www.acwing.com/problem/content/2/

思路

在0-1背包问题中，状态计算中的集合划分的方法是：将f(i,j)按照第i个物品选或不选的角度，分为两块选法：「不含第i个物品」和「含第i个物品」。

1. 「不含i」：所有物品从1到i中选，总体积不超过j，并且不包含第i个元素，等价表示为：「」；

2. 「含i」：所有物品从1到i中选，总体积不超过j，并且包含第i个元素的选法集合，等价表示为：「」，这里求解含第i个物品的最大值的思路是：由于所有选法都包含第i个物品，故「可以先把第i个物品去掉，对不包含第i个物品的求最大值，再把第i个物品加上」。

   举个例子：全班考试，考试最高分是小明。但是考试分数都太低了，那么可以给每个人都加上20分，加上20分的最高分还是小明。

   那么最终f(i,j)就可以表示为这两种情况的最大值，即：

代码

1. 先将输入元素保存到数组：

之所以要定义N+1的长度，是因为数组表示的含义是第i个元素是第i个物品。

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
// 背包的容量为V
int V = sc.nextInt();
// 一个长度为N+1的数组，第i个元素表示第i个物品的体积；
int[] v = new int[N+1] ;
// 一个长度为N+1的数组，第i个元素表示第i个物品的价值；
int[] w = new int[N+1] ;
for (int i=1 ; i <= N ; i++){
    // 接下来有 N 行，每行有两个整数:v[i],w[i]，用空格隔开，分别表示第i件物品的体积和价值
    v[i] = sc.nextInt();
    w[i] = sc.nextInt();
}
int[][] f = new int[N+1][V+1];

2. DP实现

// f(0,0->V)表示取0个物品的最大价值，初始化时为0，故从1开始
for(int i = 1; i <= N; i++){// 所有物品
    for(int j = 0; j <= V; j++){// 所有体积
        // 1. 不含i的情况
        f[i][j] = f[i-1][j];
        // 2. 含i的情况
        if(j>=v[i]) f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
    }
}
System.out.println(f[N][V]);

3. DP优化

对DP做优化，就是对动规的方程做一个等价变形。在背包中计算时，「f[i][]这一层只用到了f[i-1][]这一层的值，且在含有第i个物品的情况求算时，j-v[i]是严格小于f[j]的」。因为有层层的顺序关系，可以考虑转化为一维数组进行优化。

对原来的dp情况做等价变形：

• 不含i的情况：f[i][j] = f[i-1][j]变形为：f[j] = f[j]，因为无意义，可以将其省略；
• 含i的情况：由于原来的条件if(j>=v[i])，在j<v[i]时，判定条件无意义，因此把循环可修改为：for(int j=v[i];j<=V;j++);
• 在状态方程计算中，如果j是从小到大进行枚举，那么f[j-v[i]]在第i层已经重新更新过了，故f[j-v[i]]是等价于原来的f[i][j-v[i]]，而不是原来的f[i-1][j-v[i]]，故需要让j从大到小进行枚举，这样在第i层求算时，第i-1层还未更新；

int[] f = new int[V+1];
for(int i=1;i<=N;i++){
    for(int j=V;j>=v[i];j--){
        f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
    }
}
System.out.println(f[V]);

完全背包

题目

题目链接：https://www.acwing.com/problem/content/3/

思路

01背包问题的状态计算是按照「第i个物品选0个还是选1个」来进行集合划分，从而分成两组。而完全背包问题由于第i个物品有无限个，可以按照「第i个物品选多少」来划分，分成若干组。

因为受到大小容量V的限制，故不可能分成限组，假设第i个物品最多选k个，那么：

1. 当第i个物品选0个时：此时就是不选第i个物品，等价于从i-1个商品中选取体积不超过j的最大值f(i,j) = f(i-1, j);
2. 当第i个物品选k个时：此时按照曲线救国的方法：先去掉k个物品i，再求k的范围内的最大值：max(f(i-1, j-k*v[i]))，最后再加回来k个物品i，可以表示为：f(i,j)=f(i-1, j-k*v[i])+k*w[i], k表示为第i个物品的个数；

代码

1. 先将输入元素保存到数组：和上道一样；

2. DP实现(朴素做法)：

int[][] f = new int[N+1][V+1];
for(int i=1;i<=N;i++)
      for(int j=0;j<=V;j++)
          // k从0开始, 当k超出规定体积时结束
          for(int k=0;k*v[i]<=j;k++)
              f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
System.out.print(f[N][V]);

3. DP优化(两层循环优化)

从动态规划的转移方程入手，对于f(i, j)，可以表示为：

由f(i, j-v)做对比，可以看出对应的每一项只相差一个w，因此可以将f(i, j)等价表示为：f(i, j) = max(f(i-1, j), f(i, j-v)+w)

本来要枚举k个状态，现在只枚举两个状态即可：

int[][] f = new int[N+1][V+1];
for(int i=1;i<=N;i++)
    for(int j=0;j<=V;j++){
        f[i][j] = f[i-1][j];
        if(j>=v[i]) f[i][j] = Math.max(f[i][j], f[i][j-v[i]]+w[i]);
    }
System.out.print(f[N][V]);

4. DP优化(再一维数组优化)

同样，在这个计算时，因为有层层的顺序关系，可以考虑转化为一维数组进行优化。

对原来的dp情况做等价变形：

• 第i个物品取0个的情况：f[i][j] = f[i-1][j]变形为：f[j] = f[j]，因为无意义，可以将其省略；
• 第i个物品取k个的情况：由于原来的条件if(j>=v[i])，在j<v[i]时，判定条件无意义，因此把循环可修改为：for(int j=v[i];j<=V;j++);
• 在状态方程计算中，那么f[j-v[i]]在第i层已经重新更新过了，故f[j-v[i]]是等价于原来的f[i][j-v[i]],故原来的循环顺序不用像01背包一样改变；

int[] f = new int[V+1];
for(int i=1;i<=N;i++)
    for(int j=v[i];j<=V;j++){
        f[j] = Math.max(f[j], f[j-v[i]]+w[i]);
    }
System.out.print(f[V]);

多重背包

题目

题目链接：https://www.acwing.com/problem/content/4/

思路

思路和完全背包一致，区别只是k的范围是从0到s[i];

代码

1. 先将输入元素保存到数组：和上道一样；

2. DP实现(朴素版)

因为多重背包问题和完全背包问题的区别在于：完全背包的物品可以无限选，所以最大为k*物品体积不超过规定体积，而多重背包问题的规定是取得个数必须小于s[i]，且该个数乘以物品得体积不超过规定体积。于是可以写出朴素代码如下：

int[][] f = new int[N+1][V+1];
for(int i=1;i<=N;i++)
    for(int j=0;j<=V;j++){
        for(int k=0;k<=s[i] && k*v[i]<=j;k++)
            f[i][j] = Math.max(f[i][j], f[i-1][j-v[i]*k]+w[i]*k);
    }
System.out.print(f[N][V]);

3. DP优化

• 「能否用完全背包的形式进行优化？」

  首先回忆完全背包的优化方式，在完全背包问题的转移方程中，有：通过上述比较，可以把f(i,j)简化为：max(f(i-1)(j),f(i)(j-v)+w)。

  但是对于多重背包问题而言，状态转移方程可以写为如下形式：

  区别在于，多重背包方程多出来了最后一项，对于f(i,j-w)这个状态表达式而言，首先这个状态的含义是从前i个物品中选，且总体积不超过j-w的最大价值，我们现在最多只能选s个物品，因此如果我们选s个第i个物品，那么体积上就要减去s * v,价值上就要加上s * w，那更新到状态中去就是f(i-1,j-v-s*v)+s*w。

  而完全背包由于对每种物品没有选择个数的限制，所以只要体积够用就可以一直选，没有最后一项。

  因为存在最后一项，故n个数的最大值，不一定等价于n-1个数的最大值，故多重背包问题不能使用完全背包的方式进行优化。

• 「二进制优化方法」

  二进制优化方法的基础点在于：任意一个实数可以由二进制数来表示，也就是2^0~2^k其中一项或几项的和。那么我们可以基于这点来对多重背包问题做优化，优化的问题是：每件物品取多少件可以获得最大价值。

  举个例子：对于苹果(每件物品)，取多少个苹果呢？传统的思维是每次都拿一个来问，取了好还是不取好，一个苹果一个苹果去选，选够n个苹果就停止，这样选择的次数就是n次。

  而二进制优化思维就是将其分堆，分成k+1个分别有2^k个的堆，然后拿这一堆一堆去问，我是取了好，还是不取好？比如将这一堆苹果分别按照1,2,4,8,16,.....512分到10个箱子里，分别用这10个箱子去问，那么这样选择的次数就是10次，大幅减少了比较的次数。

• 「dp优化后的代码」

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int maxN = 200002;
int[] v = new int[maxN];
int[] w = new int[maxN];
int[] f = new int[maxN];
int cnt = 0;
for(int i=1;i<=N;i++){
    int a,b,s;
    a = sc.nextInt();
    b = sc.nextInt();
    s = sc.nextInt();
    int k = 1;
    while(k<=s){
        // k个物品打包在一起
        cnt ++;
        v[cnt] = a*k; // 堆中新物品的体积
        w[cnt] = b*k;
        s-=k; // k从s值中减去
        k*=2;
    }
    // 剩余的值为s-前二进制的和
    if(s>0){
        cnt++;
        v[cnt] = a*s;
        w[cnt] = b*s;
    }
}
N = cnt;
// 转化为01背包问题
for(int i=1;i<=N;i++)
    for(int j=V;j>=v[i];j--)
        f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
System.out.print(f[V]);

分组背包

题目

题目链接：https://www.acwing.com/problem/content/9/

思路

代码

如果转移时用的是上一层的状态，那么就从大到小来枚举体积；如果是用的本层的状态，就需要从小到大来枚举体积。

for(int i=1;i<=n;i++){
    for(int j=m;j>=0;j--){
        for(int k=0; k<s[i];k++){
            if(v[i][k]<=j){
                f[j] = Math.max(f[j],f[j-v[i][k]]+w[i][k]);
            }
        }
    }
}
System.out.print(f[m]);