01背包
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 v[i]，价值是 w[i]。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
01背部的特征是每个物品都只有一件，要么选择装进背包要么选择不装进背部。
首先是状态表示，一般都能想到的是二维数组来表示状态dp[i][j]，这个应该表示的是从前i个物品中选取，总体积是j的情况下，总价值最大是多少。
那么可以知道这道题的答案就是dp[N][V]了。
然后是状态转移了。
从题目就可以看出选择的方案，或者说是状态转移的方案。
不选择第i件物品，即可以理解为从第i - 1件物品中选择，不选择第i件物品了，背包容量不变。
dp[i][j] = dp[i - 1][j]
选择第i件物品，即可以理解选择了第i - 1件物品之后，从第i - 1件物品中选择，背包容量变为原容量减去第i件物品的体积，这个方案的前提是当前背包容量大于物品的体积。
dp[i][j] = dp[i - 1][j - v[i]] + w[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
| import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if(j >= v[i]){
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
}else{
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[N][V]);
}
}
|
优化dp数组。
这里使用的是二维的dp数组表示状态，但其实可以优化成一维的数组。
仔细观察这两个方程的状态转移方程。
dp[i][j] = dp[i - 1][j]dp[i][j] = dp[i - 1][j - v[i]] + w[i]
第一个很好理解，将第i - 1的层j状态转移到第i层，但因为总体积是不变的，即j是不变的，所以这个转移相当于没有意义，所以遍历了i层这个转移就自动成立了。
第二个就会有点麻烦。当我们想要更新当前的状态，那么就需要第i -1层的[j - v[i]] + w[i]数据来更新，如果我们直接使用d[j] = dp[j - v[i]] + w[i]是不对的。
这个式子其实等价于dp[i][j] = dp[i][j - v[i]] + w[i]，与之前的状态转移是不一样的，所以是不对的，要想这个式子与之前的状态转移方程等价，将体积从V到0遍历就可以了。
1
2
3
4
5
6
7
8
9
10
11
| for (int i = 1; i <= N; i++) {
for (int j = V; j >= 0; j--) {
if(j >= v[i]){
dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
}else{
dp[j] = dp[j];
}
}
}
|
故完整的代码为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
for (int j = V; j >= v[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
}
}
System.out.println(dp[V]);
}
}
|
为什么逆序遍历可以让上述两个式子等价呢？
遍历第i层的时候，dp[j-v[i]]会用到之前的状态，这个式子其实等价于dp[i][j-v[i]]，在同一层里，用到了之前的状态，而不是上一层i - 1的状态，这就会导致i这个物品是被用到了第二次的，而01背包是每个物品只能用一次的，所以这个式子是不对的，逆序遍历体积容量的话就不会用到被污染的数据，就让式子成立了。（是有点绕，以后理解更深了在来修改一下说法）
还可以进一步优化输入，即便输入边处理数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
int vi = sc.nextInt();
int wi = sc.nextInt();
for (int j = V; j >= vi; j--) {
dp[j] = Math.max(dp[j], dp[j-vi] + wi);
}
}
System.out.println(dp[V]);
}
}
|
完全背包
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
完全背包与01背包不一样的是完全背包是可以选无限件的。
所以完全背包与01背包分析不一样的就是状态的转移方案。
01背包问题里，是有两种方案的，选一个或者是不选，完全背包就会有很多种方案。
不选第i件物品
dp[i][j] = dp[i - 1][j]
选择k件第i个物品，容量要大于体积。
dp[i][j] = dp[i - 1][j - v[i]] + w[i]
跟01背包差不多，直接遍历所有第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
| import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for (int i = 1;i <= N; i++) {
for (int j = 0; j <= V; j++) {
for(int k = 0 ; k * v[i] <= j ; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
System.out.println(dp[N][V]);
}
}
|
这里用到了三重循环，这样的话时间复杂度会很高，所以应该要考虑进行优化。
仔细观察一下这个状态转移方程。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v] + w, dp[i - 1][j - 2v] + 2w....)
我们求dp[i][j]的最大值也就是求后面这些方案的最大值，我们可以注意到
dp[i][j - v] = max(dp[i - 1][j - v], dp[i - 1][j - 2v] + w)....
所以通过二式我们可以求出一式后面的除了第一项的最大值。
故进行优化之后的状态状态方程为
dp[i][j] = max(dp[i - 1][j], dp[i][j - v] + w)
这样就能省去一重循环，于是变成下面这样。
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.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for (int i = 1;i <= N; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i]) {
dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
}
System.out.println(dp[N][V]);
}
}
|
变成这样会发现和01背包十分相似，所以也可以根据01背包的优化思路进行优化，先将该状态数组优化为一维。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for (int i = 1;i <= N; i++) {
for (int j = v[i]; j <= V; j++) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.println(dp[V]);
}
}
|
在优化下输入，便输入边处理 ，最终可以为这样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
for (int j = v; j <= V; j++) {
dp[j] = Math.max(dp[j],dp[j - v] + w);
}
}
System.out.println(dp[V]);
}
}
|
多重背包
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
多重背包跟完全背包不一样的点是多重背包的每件物品是有个数限制的，不过大体是和完全背包差不多的解题思路。
暴力三重循环
首先是最暴力的方式，三重循环，多重背包的三重循环相对于完全背包就是为第三个循环加多一个条件就好了。
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
| import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
int[] s = new int[N + 1];
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
for (int i = 1;i <= N; i++) {
for (int j = 0; j <= V; j++) {
for(int k = 0 ; k * v[i] <= j && k <= s[i] ; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
System.out.println(dp[N][V]);
}
}
|
三重循环的时间复杂度为O(n^3)，很大概率会超时，所以要进行优化才行。
二进制优化
其实多重背包可以转换成01背包的问题，只要将背包的个数拆分开来就可以了。
最容易想到的是将n件商品拆分成n个商品，这样将所有商品个数大于1的商品全部拆分，就可以理解为01背包的问题了，选或者是不选。
但是这种方案是行不通的。因为将n件商品拆分成n个，时间复杂度依旧很大，依然很容易超时，所以我们得考虑出另一种拆分方法，怎样拆分能用拆分后得数字表示出0 ~ n呢？
这就用到了一种二进制的拆分方法。
将数字转换成类似二进制的表示方法。
比如要拆分9这个数字
我们可以拆分为 1 + 2 + 4 + 2
最后一个数小于2的n次方就使用剩余的数
这样多重背包的一个9件的商品问题就可以拆分为01背包的四个不同的商品的问题
使用这四个数选或者不选两种方案就能遍历出0 ~ 9十种方案
接下来看代码。
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
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
List<Integer> vi = new ArrayList<>();
List<Integer> wi = new ArrayList<>();
for (int i = 0; i < N; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
int s = sc.nextInt();
for (int k = 1; k < s; k *= 2) {
vi.add(k * v);
wi.add(k * w);
s = s - k;
}
if (s > 0) {
vi.add(s * v);
wi.add(s * w);
}
}
int[] dp = new int[V + 1];
for (int i = 0; i < vi.size(); i++) {
for (int j = V; j >= vi.get(i); j--) {
dp[j] = Math.max(dp[j],dp[j - vi.get(i)] + wi.get(i));
}
}
System.out.println(dp[V]);
}
}
|
参考链接
