01背包问题

来源：AcWing
链接：https://www.acwing.com/problem/content/2/

问题叙述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0< N,V ≤ 1000
0< vi,wi ≤ 1000

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
8

分析

01背包的模板题
每种物品只有选与不选两种状态，

  • 如果不选，则维持上一个状态
  • 如果选，则需要留出对应的空间
    逆序遍历

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] dp = new int[m + 1];
        for (int i = 0; i < n; i++) {
            int volume = scan.nextInt();
            int val = scan.nextInt();
            for (int j = m; j >= volume; j--) {
                dp[j] = Math.max(dp[j],dp[j - volume] + val);
            }
        }
        System.out.println(dp[m]);
    }
}

完全背包问题

来源：AcWing
链接：https://www.acwing.com/problem/content/3/

问题叙述

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
10

分析

完全背包的模板题
与01背包问题唯一的区别是正序遍历

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] dp = new int[m + 1];
        for (int i = 0; i < n; i++) {
            int volume = scan.nextInt();
            int val = scan.nextInt();
            for (int j = volume; j <= m; j++) {
                dp[j] = Math.max(dp[j], dp[j - volume] + val);
            }
        }
        System.out.println(dp[m]);
    }
}

多重背包问题I

来源：AcWing
链接：https://www.acwing.com/problem/content/4/

问题叙述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
0 < N,V ≤ 100
0 < vi,wi,si ≤ 100
输入样例

1
2
3
4
5
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

1
10

分析

朴素版的多重背包问题直接用三层循环，把它当成01背包问题，最内层循环遍历一下物品个数

  • 选择 0 件物品的最大价值，即dp[i];
  • 选择 1 件物品的最大价值，即dp[i - vol[i] * 1] + wor[i] * 1;
  • 选择 2 件物品的最大价值，即dp[i - vol[i] * 3] + wor[i] * 3;
  • 选择 3 件物品的最大价值，即dp[i - vol[i] * 3] + wor[i] * 3;
  • 选择 s 件物品的最大价值，即dp[i - vol[i] * s] + wor[i] * s;

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] dp = new int[m + 1];
        for (int i = 0; i < n; i++) {
            int v = scan.nextInt(), w = scan.nextInt(), s = scan.nextInt();
            for (int j = m; j >= 1; j--) {
                for (int k = 1; k <= s && k * v <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * v] + k * w);
                }
            }
        }
        System.out.println(dp[m]);
    }
}

多重背包问题II

来源：AcWing
链接：https://www.acwing.com/problem/content/5/

问题叙述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
0 < N ≤ 1000
0 < V ≤ 2000
0 < vi,wi,si ≤ 2000

提示：
本题考查多重背包的二进制优化方法。

输入样例

1
2
3
4
5
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

1
10

分析

由于数据范围扩大，朴素版的多重背包问题时间复杂度为O(n^3)，会超时

所以这里采用二进制优化，转化成01背包问题。

二进制拆分思想:
将第i种物品拆分成若干件物品，每件物品的体积和价值乘以一个拆分系数（1,2^1,2^2 … 2^k-1, s-2^k+1），就可以转化成01背包的物品求解。例如，si=12，拆分系数为1,2,4,5，转化成4件01背包的物品:(v, w)，(2v, 2w)，(4v, 4w)，(5v, 5w)

假设有50个苹果，现在要取n个苹果（n≤50），如何取? 朴素的做法应该是将苹果一个一个拿出来，直到n个苹果被取出来。
再假设有50个苹果和6只箱子，利用箱子进行某些预备工作，可以在每个箱子中放2^k处(k≥0)个苹果，也就是1、2、4、8、16、19（剩余的数），取任意n个苹果时，只要推出几只箱子就可以了。

我们只需要遍历1、2、4、8、16、19这几个数，就能拼凑出1~50中的所有数

Code

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
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] dp = new int[m + 1];
        ArrayList<Integer> worth = new ArrayList<>();
        ArrayList<Integer> volume = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int v = scan.nextInt(), w = scan.nextInt(), s = scan.nextInt();
            for (int k = 1; k <= s; k *= 2) {
                s -= k;
                volume.add(v * k);
                worth.add(w * k);
            }
            if (s > 0) {
                volume.add(v * s);
                worth.add(w * s);
            }
        }
        for (int i = 0; i < worth.size(); i++) {
            for (int j = m; j >= volume.get(i); j--) {
                dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i));
            }
        }
        System.out.println(dp[m]);
    }
}

混合背包问题

来源：AcWing
链接：https://www.acwing.com/problem/content/7/

问题叙述

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

si = −1 表示第 i 种物品只能用1次；
si = 0 表示第 i 种物品可以用无限次；
si > 0 表示第 i 种物品可以使用 si 次；

输出格式
输出一个整数，表示最大价值。

数据范围
0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
−1 ≤ si ≤ 1000

输入样例

1
2
3
4
5
4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：

1
8

分析

混合背包就是将前面的01背包，完全背包，多重背包混合到一块

si = −1 表示第 i 种物品只能用1次； --> 01背包问题
si = 0 表示第 i 种物品可以用无限次； --> 完全背包问题
si > 0 表示第 i 种物品可以使用 si 次； --> 多重背包问题

利用分类处理的思想:

  1. 利用多重背包的二进制优化，可以先将多重背包转化为多个01背包。
  2. 用vol, wor, type三个数组来记录转化之后的所有背包的体积、价值、类型，type为0表示完全背包，type为-1表示01背包
  3. 最后做一遍，以type的值分为两类，做完全背包和01背包。

Code

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
47
48
import java.util.*;

class Things {
    int vol;
    int wor;
    int type;

    public Things(int vol, int wor, int type) {
        this.vol = vol;
        this.wor = wor;
        this.type = type;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] dp = new int[m + 1];
        ArrayList<Things> things = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int v = scan.nextInt(), w = scan.nextInt(), s = scan.nextInt();
            //如果是完全背包或者01背包
            if (s <= 0)
                things.add(new Things(v, w, s));
            //如果是多重背包，就先进行二进制优化，然后转化成01背包
            else {
                for (int j = 1; j <= s; j *= 2) {
                    s -= j;
                    things.add(new Things(v * j, w * j, -1));
                }
                if (s > 0) things.add(new Things(v * s, w * s, -1));
            }
        }

        for (Things t : things) {
            //type为-1，按照01背包做，逆序遍历
            if (t.type == -1)
                for (int i = m; i >= t.vol; i--)
                    dp[i] = Math.max(dp[i], dp[i - t.vol] + t.wor);
            //type为0，按照完全背包做，正序遍历
            if (t.type == 0)
                for (int i = t.vol; i <= m; i++)
                    dp[i] = Math.max(dp[i], dp[i - t.vol] + t.wor);
        }
        System.out.println(dp[m]);
    }
}

二维费用的背包问题

来源：AcWing
链接：https://www.acwing.com/problem/content/8/

问题叙述

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0 < N ≤ 1000
0 < V,M ≤ 100
0 < vi,mi ≤ 100
0 < wi ≤ 1000

输入样例

1
2
3
4
5
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例

1
8

分析

多了一条限制的01背包问题，那就再加一层循环

dp[i][j]表示容积为i，承重为j的背包，可装下的最大价值

状态转移方程为dp[i][j] = Math.max(dp[j][k], dp[j - volume][k - weight] + value);

由于是01背包问题，所以依旧是逆序遍历

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), v = scan.nextInt(), w = scan.nextInt();
        int[][] dp = new int[v + 10][w + 10];
        for (int i = 0; i < n; i++) {
            int a = scan.nextInt(), b = scan.nextInt(), c = scan.nextInt();
            for (int j = v; j >= a; j--) {
                for (int k = w; k >= b; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - a][k - b] + c);
                }
            }
        }
        System.out.println(dp[v][w]);
    }
}

分组背包问题

来源：AcWing
链接：https://www.acwing.com/problem/content/9/

问题叙述

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。

数据范围
0 < N,V ≤ 100
0 < Si ≤ 100
0 < vij,wij ≤ 100

输入样例

1
2
3
4
5
6
7
8
3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：

1
8

分析

只能采用「枚举物品 - 枚举容量 - 枚举决策」的朴素思路来求解。也就是需要三层循环

由于每组有若干个物品，且每组「最多」选择一件物品。

那么对于第i组而言，可决策的方案如下

  • 啥也不选 --> dp[j] = dp[j]

  • 选改组的第一个物品 --> dp[j] = dp[j - volume[0]] + value[0];

  • 选改组的第一个物品 --> dp[j] = dp[j - volume[1]] + value[1];

  • 选改组的第n个物品 --> dp[j] = dp[j - volume[n]] + value[n];

最终我们的dp[j]就是从所有方案中选取max

Code

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
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), v = scan.nextInt();
        int[] dp = new int[v + 10];
        int[] volume = new int[v + 10];
        int[] value = new int[v + 10];
        for (int i = 0; i < n; i++) {
            int s = scan.nextInt();
            for (int j = 0; j < s; j++) {
                volume[j] = scan.nextInt();
                value[j] = scan.nextInt();
            }
            for (int j = v; j >= 0; j--) {
                for (int k = 0; k < s; k++) {
                    if (j >= volume[k])
                        dp[j] = Math.max(dp[j], dp[j - volume[k]] + value[k]);
                }
            }
        }
        System.out.println(dp[v]);
    }
}