01背包

动态规划：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的空间，则此时的j为4-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]);
    }
}