动态规划之背包问题

文章目录

前言
一、认识背包问题（简洁说明）
二、01背包
AcWing 2. 01背包问题（模板题）
三、完全背包问题
AcWing 3. 完全背包问题（模板题，含优化）
四、多重背包问题
AcWing 4. 多重背包问题 I（模板题，可三重循环暴力）
AcWing 5. 多重背包问题 II（模板题，二进制优化为01背包问题）
五、分组背包问题
AcWing 9. 分组背包问题（模板题）
参考文章

前言

目前在学习AcWing课程的算法基础课，当前博客中主要包含背包类问题的模板题，之后会陆续更新一些相对应题目的题单。

当前文章已收录到博客文件目录索引：博客目录索引(持续更新)

一、认识背包问题（简洁说明）

①01背包（每件物品能选一次或不选）：每件物品最后多只用一次。

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn，每种物品有且只有一个。
在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

②完全背包：每件物品有无限个。

③多重背包（含优化）：每件物品最多有有限个，题目给出限制。

④分组背包：有多组，每一组里面可以选一个。

二、01背包

AcWing 2. 01背包问题（模板题）

题目链接：AcWing 2. 01背包问题

分析：

题解：

二维数组：

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n^2^)

import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] fn = new int[N][N];
    static int n, m;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 1; i <= n; i ++) {
            ss = cin.readLine().split(" ");
            v[i] = Integer.parseInt(ss[0]);
            w[i] = Integer.parseInt(ss[1]);
        }
        //初始化默认为0
        //dp状态转移
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                //不选
                fn[i][j] = fn[i - 1][j];
                if (j >= v[i]) {
                    //选
                    fn[i][j] = Math.max(fn[i][j], fn[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        //最大装的重量
        System.out.println(fn[n][m]);
    }
    
}

一维数组（优化）：改成一维数组的滚动数组时，需要将第二层遍历m循环从后往前，若是从前往后的话fn[j - v[i]]就会使用到最新已更新的数据，而不是上一层旧的数据

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[] fn = new int[N];
    static int n, m;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 1; i <= n; i ++) {
            ss = cin.readLine().split(" ");
            v[i] = Integer.parseInt(ss[0]);
            w[i] = Integer.parseInt(ss[1]);
        }
        //初始化默认为0
        //dp状态转移
        for (int i = 1; i <= n; i ++) {
            //为了上一层数据不被覆盖为新的，从后往前来进行更新背包最大重量
            for (int j = m; j >= 1; j --) {
                //不选
                //fn[j] = fn[j];
                if (j >= v[i]) {
                    //选
                    fn[j] = Math.max(fn[j], fn[j - v[i]] + w[i]);
                }
            }
        }
        //最大装的重量
        System.out.println(fn[m]);
    }
    
}

三、完全背包问题

AcWing 3. 完全背包问题（模板题，含优化）

题目链接：AcWing 3. 完全背包问题

复杂度分析：时间复杂度O(n^3^)；空间复杂度O(n^2^)

import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] fn = new int[N][N];
    static int n, m;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 1; i <= n; i ++) {
            ss = cin.readLine().split(" ");
            v[i] = Integer.parseInt(ss[0]);
            w[i] = Integer.parseInt(ss[1]);
        }
        //多种循环
        for (int i = 1; i <= n; i ++) {  //前i个物品
            for (int j = 0; j <= m; j ++) {  //体积为k
                int t = j / v[i];//计算最多装多少个物品i
                for (int k = 0; k <= t; k ++) { //多个物品
                    //由于k是从0开始的，所以我们可省略该句
                    //fn[i][j] = Math.max(fn[i][j], fn[i - 1][j]);
                    //不拿当前第i个物品；拿当前第i个物品k个
                    fn[i][j] = Math.max (fn[i][j], fn[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
        System.out.println(fn[n][m]);
    }
    
}

三重循环优化为两重循环：

我们将j - k * v[i]看作变量v。

目标转移方程：dp[i][j]= max(dp[i - 1][j], dp[i - 1][j - v] + w, dp[i - 1][j - 2 * v] + 2 * w, dp[i - 1][j - 3 * v] + 3 * w, ...);

而我们可以发现在上面方程之前：dp[i][j - v] = max(dp[i - 1][j - v], dp[i - 1][j - 2 * v] + w, dp[i - 1][j - 3 * v] + 2 * w, .....)；

那么我们可以将目标转移方程优化为：dp[i][j]= max(dp[i - 1][j], dp[i][j - v] + w)

import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] fn = new int[N][N];
    static int n, m;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 1; i <= n; i ++) {
            ss = cin.readLine().split(" ");
            v[i] = Integer.parseInt(ss[0]);
            w[i] = Integer.parseInt(ss[1]);
        }
        //多种循环
        for (int i = 1; i <= n; i ++) {  //前i个物品
            for (int j = 0; j <= m; j ++) {  //体积为k
                fn[i][j] = fn[i - 1][j];
                //优化
                if (j >= v[i])
                    fn[i][j] = Math.max (fn[i][j], fn[i][j - v[i]] + w[i]);
            }
        }
        System.out.println(fn[n][m]);
    }
    
}

优化空间二维为一维（滚动数组）：

import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[] fn = new int[N];
    static int n, m;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 1; i <= n; i ++) {
            ss = cin.readLine().split(" ");
            v[i] = Integer.parseInt(ss[0]);
            w[i] = Integer.parseInt(ss[1]);
        }
        //多种循环
        for (int i = 1; i <= n; i ++) {  //前i个物品
            for (int j = 0; j <= m; j ++) {  //体积为k
                //优化
                if (j >= v[i])
                    fn[j] = Math.max (fn[j], fn[j - v[i]] + w[i]);
            }
        }
        System.out.println(fn[m]);
    }
    
}

对应与01背包的区别：上01、下完全

四、多重背包问题

AcWing 4. 多重背包问题 I（模板题，可三重循环暴力）

题目链接：AcWing 4. 多重背包问题 I

分析

与完全背包类似，这里给定了我们每个物品的指定数量，所以我们无需进行自行计算每个物品最大的数量了，直接三重循环暴力走一波。

由于N,V给的数量不大，三重循环也能够通过。

题解

复杂度分析：时间复杂度O(n^3^)；空间复杂度O(n^2^)

import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 110;
    static int[] v = new int[N], w = new int[N], s = new int[N];
    static int[][] fn = new int[N][N];
    static int n, m;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 1; i <= n; i ++) {
            ss = cin.readLine().split(" ");
            v[i] = Integer.parseInt(ss[0]);
            w[i] = Integer.parseInt(ss[1]);
            s[i] = Integer.parseInt(ss[2]);
        }
        //多种循环
        for (int i = 1; i <= n; i ++) {  //前i个物品
            for (int j = 0; j <= m; j ++) {  //体积为k
                //指定物品的数量（注意：k * v[i] <= j范围下进行选择）
                for (int k = 0; k <= s[i] && k * v[i] <= j; k ++) {
                    //由于k从0开始的，所以可以进行省略
                    //fn[i][j] = Math.max(fn[i][j], fn[i - 1][j]);
                    fn[i][j] = Math.max (fn[i][j], fn[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
        System.out.println(fn[n][m]);
    }
    
}

AcWing 5. 多重背包问题 II（模板题，二进制优化为01背包问题）

题目链接：AcWing 5. 多重背包问题 II

分析

简述：利用二进制去将1个物品s个数量优化为logs个组合箱子数，接着就是一个01背包思路解决方案。

将多重背包问题去优化为01背包问题。

问题1：为什么多重背包问题会多出来一项？

//完全背包问题
dp[i][j]= max(dp[i - 1][j], dp[i - 1][j - v] + w, dp[i - 1][j - 2 * v] + 2 * w, dp[i - 1][j - 3 * v] + 3 * w, ...);
dp[i][j - v] = max(dp[i - 1][j - v], dp[i - 1][j - 2 * v] + w, dp[i - 1][j - 3 * v] + 2 * w, .....)；
最终优化为：dp[i][j]= max(dp[i - 1][j], dp[i][j - v] + w)
    
//多重背包问题
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v] + w, dp[i - 1][j - 2v] + 2w, dp[i - 1][j - 3v] + 3w, ..., dp[i - 1][j - sv] + sw)
dp[i][j - v] = max(dp[i - 1][j - v], dp[i - 1][j - 2v] + w, dp[i - 1][j - 3v] + 2w, ..., dp[i - 1][j - sv] + (s - 1)w, dp[i - 1][j - (s + 1)v] + sw)

注意：这边多重背包多出来一项dp[i - 1][j - (s + 1)v] + sw，什么原因呢？因为针对于dp[i][j - v]同样也是来看做是从0*v[i] 不断减到s*v[i]，所以最后一个为j - v - s*v[i] = j - (s + 1)v。

问题2：不能用完全背包问题解法来解决的原因？

给定我们所有数的最大值，能够根据最后一个最大值来求出来前面元素的最大值呢？

这个是不能求得的，不能做减法的，max是不能做减法的，加法是可以做出来的。
若是最大值，我们并不能通过总共的最大值和最后1个最大值来求出来前面的最大值，所以不能够使用完全背包问题解决。

问题3：二进制优化的点在哪里，如何进行优化？

原本的暴力做法时间复杂度为O(n * m * s)，可以通过组合形式来压缩计算的次数。

这里拿一个案例说明：取自博客动态规划专题——背包问题

针对于根据给定的每个物品s数量，我们来将一个物品s个数量去拆为logs组，即原本要暴力求得n*s转为n*logn

//实现代码
int a,b,s;
cin >> a >> b >> s;
int k = 1; // 组别里面的个数
while(k<=s)
{
    cnt ++ ; //组别先增加
    v[cnt] = a * k ; //整体体积
    w[cnt] = b * k; // 整体价值
    s -= k; // s要减小
    k *= 2; // 组别里的个数增加
}
//剩余的一组
if(s>0)
{
    cnt ++ ;
    v[cnt] = a*s; 
    w[cnt] = b*s;
}

//举实际案例
//案例1：重量为4，价值为3，数量为5
//对应的1个物品数量5个，拆分多组5 => 1 2 2    后面分别表示1组1个，1组2个，1组2个，可以由这三组构成数量0-5任何一个数
1 <= 5    cnt = 0, v[0] = 4, w[0] = 3, s = 4, k = 2
2 <= 4    cnt = 1, v[1] = 8, w[1] = 6, s = 2, k = 4
//由于此时4>2，所以这里单独取s剩余数
cnt = 2, v[2]=2*4=8，w[2]=2*3=6 
    
//举例2：重量为4，价值为3，数量为7
//对应的1个物品数量7个，拆分多组7 => 1 2 4    后面分别表示1组1个，1组2个，1组4个，可以由这三组构成数量0-7任何一个数
1 <= 7    cnt = 0, v[0] = 4, w[0] = 3, s = 6, k = 2
2 <= 6    cnt = 1, v[1] = 8, w[2] = 6, s = 4, k = 4
4 <= 4    cnt = 2, v[2] = 16, w[2] = 12, s = 0, k = 8
//结束

最终我们对目标重量来进行依次枚举m次，此时时间复杂度为O(n*logns*m)，原本O(n*m*s)需要运行40亿次，此时优化为两千四百万样子，即可AC。

题解

复杂度分析：时间复杂度O(n*logns*m)；空间复杂度O(n*logns)

import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 12010, M = 2010;//N表示n*logs，1000 * 12 + 10，M表示最大的体积重量
    static int[] v = new int[N], w = new int[N];//空间都为总组数
    static int[] fn = new int[M];//一维滚动数组优化，这里数量为体积大小
    static int n, m;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        int cnt = 0;//最终的总组数
        //读取每组的体积和质量
        for (int i = 1; i <= n; i ++) {
            ss = cin.readLine().split(" ");
            int vv = Integer.parseInt(ss[0]);
            int ww = Integer.parseInt(ss[1]);
            int s = Integer.parseInt(ss[2]);
            int k = 1;
            //根据s来分配每组物品的数量
            while (k <= s) {
                cnt ++;
                v[cnt] = k * vv;
                w[cnt] = k * ww;
                s -= k;//减去总数
                k *= 2;//2的倍乘
            }
            //处理多余的s
            if (s > 0) {
                cnt ++;
                v[cnt] = s * vv;
                w[cnt] = s * ww;
            }
        }
        
        //01背包问题解决方案
        for (int i = 1; i <= cnt; i ++) { //总数量为cnt个
            //滚动一维数组需要从后往前
            for (int j = m; j >= v[i]; j --) {
                fn[j] = Math.max(fn[j], fn[j - v[i]] + w[i]);
            }
        }
        System.out.println(fn[m]);
    }
}

五、分组背包问题

AcWing 9. 分组背包问题（模板题）

题目链接：AcWing 9. 分组背包问题

分析

分组背包：有多组，每一组里面可以选一个。

以第i组为单位来进行选，多加一层循环遍历组内的物品，本质还是01背包问题。

题解

复杂度分析：时间复杂度O(n^3^)；空间复杂度O(n^2^)

import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 110;
    static int[][] v = new int[N][N], w = new int[N][N];//重量和价值在指定i组k个 v[i][k]  w[i][k]
    static int[] fn = new int[N];//滚动数组
    static int[] s = new int[N];//记录每组的数量
    static int n, m;//组数，重量
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 1; i <= n; i ++) {
            s[i] = Integer.parseInt(cin.readLine());
            //读取每组的物品
            for (int j = 0; j < s[i]; j ++) {
                ss = cin.readLine().split(" ");
                v[i][j] = Integer.parseInt(ss[0]);
                w[i][j] = Integer.parseInt(ss[1]);
            }
        }
        //dp
        for (int i = 1; i <= n; i ++) {  //遍历前i组
            for (int j = m; j >= 0; j --) {  //体积重量 滚动数组，从后往前(01背包)
                for (int k = 0; k < s[i]; k ++) { //组内第k个
                    //必须放在for循环内部，否则会直接提前结束
                    if (j >= v[i][k]) {
                        fn[j] = Math.max(fn[j], fn[j - v[i][k]] + w[i][k]);
                    }
                }
            }
        }
        System.out.println(fn[m]);
    }
    
}

参考文章

[1]. 动态规划专题——背包问题：通俗易懂十分详细，尤其是其中的多重背包问题优化。

[2]. AcWing 5. 二进制优化，它为什么正确，为什么合理，凭什么可以这样分？？：关于多重背包问题的疑问和解答比较详细，推荐。

[3]. AcWing 9. 分组背包问题（算法基础课）：y总分组背包视频讲解

前言

一、认识背包问题（简洁说明）

二、01背包

AcWing 2. 01背包问题（模板题）

三、完全背包问题

AcWing 3. 完全背包问题（模板题，含优化）

四、多重背包问题

AcWing 4. 多重背包问题 I（模板题，可三重循环暴力）

AcWing 5. 多重背包问题 II（模板题，二进制优化为01背包问题）

五、分组背包问题

AcWing 9. 分组背包问题（模板题）

参考文章

评论区请在客户端页面查看