少女祈祷中...

动态规划:01背包理论基础(一)

背包分类图

01背包

什么是01背包?

01背包

n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

关于其他背包

  • 除01背包以外其他类型的背包,面试几乎不会问,都是竞赛级别的了,leetcode上连多重背包的题目都没有,所以题库也告诉我们,01背包和完全背包就够用了。
  • 而完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。
  • 所以背包问题的理论基础重中之重是01背包,一定要理解透!

举个栗子

weight = [1, 3, 4]
value = [15, 20, 30]

注:下面所出现的数字都以此例子为例

二维dp数组01背包

动态规划五步曲:

  1. 确定dp数组以及下标的含义

我们有两个维度需要分别表示:物品和背包容量,即有0-i个放入j容量的背包所拿到的最大价值,其中0-i个物品皆可选择是否放入,且物品唯一,如下图:
01背包
(如果想用j 表示物品,j表示背包容量 行不行? 都可以的,个人习惯而已)
然后我们来逐一分析一下:

首先是把物品0放入背包的情况,weight[0] = 1, value[0] = 15:
01背包
背包容量为0,放不下物品0,此时背包里的价值为0。

背包容量为1,可以放下物品0,此时背包里的价值为15.

背包容量为2,依然可以放下物品0 (注意 01背包里物品只有一个),此时背包里的价值为15。
以此类推。

然后是0物品和1物品同时有的情况:
01背包
背包容量为 0,放不下物品0 或者物品1,此时背包里的价值为0。
背包容量为 1,只能放下物品0,背包里的价值为15。

背包容量为 2,只能放下物品0,背包里的价值为15。

背包容量为 3,上一行同一状态,背包只能放物品0,这次也可以选择物品1了,背包可以放物品1 或者 物品0,物品1价值更大,背包里的价值为20。

背包容量为 4,上一行同一状态,背包只能放物品0,这次也可以选择物品1了,背包可以放下物品0 和 物品1,背包价值为35。

通过这个举例,我们来进一步明确dp数组的含义。
dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。

  1. 确定递推公式

对于递推公式,首先我们要明确有哪些方向可以推导出dp[i][j]
这里我们以dp[1][4]为例:
首先我们有物品0和物品1,dp[1][4]有两种情况:放物品1?还是不放物品1?

如果不放物品1,则背包价值应该为dp[0][4],如果物品1,则我们应该预先留出放物品1的空间,则此时的j4-weight[1],且我们是没有放物品1的,则此时的i
i-1,则我们推出了两种dp[1][4]的来源,此时我们只需要取其最大价值即可。即递推方程为:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

  1. dp数组初始化
    首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。如图:
    01背包

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i是由 i-1推导出来,那么i为0的时候就一定要初始化。

dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

那么很明显当j < weight[0]的时候dp[0][j]应该是 0,因为背包容量比编号0的物品重量还小。

j >= weight[0]dp[0][j]应该是value[0],因为背包容量放足够放编号0物品。

代码如下:

1
2
3
4
5
6
7
8
//在创建数组时就已经初始为0了 ,可以省略
for(int j = 0; j < weight[0]; j++){
dp[0][j] = 0;
}

for(int j = weight[0]; j <= bagWeight; j++){
dp[0][j] = value[0];
}

结果如下图:
01背包

  1. 确定遍历顺序

由递推公式可知dp[i][j]由它二维数组的左上方推演而来,则其先遍历背包容量或者先遍历物品都是可以的,看自己习惯。

  1. 举例推导dp数组

自己在纸上推演,再来写代码,结果如图:
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int bagWeight = scanner.nextInt();

//定义两个数组用于接收给定数据
int[] weight = new int[n];
int[] value = new int[n];

//接收键盘端传入的两个数组
for (int i = 0; i < n; ++i) {
weight[i] = scanner.nextInt();
}
for (int j = 0; j < n; ++j) {
value[j] = scanner.nextInt();
}

//根据上述分析去定义dp数组
int[][] dp = new int[n][bagWeight + 1];

//对dp数组进行初始化
for (int j = weight[0]; j <= bagWeight; j++) {
dp[0][j] = value[0];
}

//递推遍历数组
for (int i = 1; i < n; i++) {
for (int j = 0; j <= bagWeight; j++) {
//如果当前的物品重量大于背包容量,则dp取值为不放入i物品的最大价值,即dp[i][j] = dp[i - 1][j]
if (j < weight[i]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}

//输出结果[n-1]为从数组中任取的0-i元素,[bagWeight]为背包的最大容量,结果为最大价值
System.out.println(dp[n - 1][bagWeight]);
}
}