刷题日志--背包问题 6.6
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
54 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
17import 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
54 5
1 2
2 4
3 4
4 5
输出样例:1
10
分析
完全背包的模板题
与01背包问题唯一的区别是正序遍历
Code
1 | import java.util.*; |
多重背包问题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
54 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
18import 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
54 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 | import java.util.*; |
混合背包问题
来源: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
54 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 次; —> 多重背包问题
利用分类处理的思想:
- 利用多重背包的二进制优化,可以先将多重背包转化为多个01背包。
- 用vol, wor, type三个数组来记录转化之后的所有背包的体积、价值、类型,type为0表示完全背包,type为-1表示01背包
- 最后做一遍,以type的值分为两类,做完全背包和01背包。
Code
1 | import java.util.*; |
二维费用的背包问题
来源: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
54 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 | import java.util.*; |
分组背包问题
来源: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
83 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 | import java.util.*; |