一文教会01背包

2023-11-17 09:39:04

01背包

01背包指的是一种题目模板

如果说有很多东西每个东西只能拿一次要装到一个背包里背包有体积上限

这就是经典的01背包问题

在我们下意识背出模板的时候

我们先想一下 01背包问题的暴力解法是什么

在01背包中对于每件物品要么取要么不取所以一共有2^n种情况

这是回溯+爆搜的做法

为了优化时间复杂度我们引入了动态规划(DP)

为了解释动态规划

我决定引入一个DP五部曲的概念（——摘自《代码随想录》）

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

下面是01背包的模板题

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

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

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

输入格式

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

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

输出格式

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

数据范围

0 < N , V ≤ 1000 0<N,V≤1000 0<N,V≤1000

0 < v i , w i ≤ 1000 0<vi,wi≤1000 0<vi,wi≤1000

输入样例

输出样例：

朴素的做法是这样的

 	int n, V;
    cin >> n >> V;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
    	for(int j = 1; j <= V; j++)
    	{ 
    		if(j >= v[i])	dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
    		else	dp[i][j] = dp[i-1][j];
    	}
    	
    cout << dp[n][V] << endl;

对于背包问题其实状态都是可以压缩的

在使用二维数组的时候，递推公式：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实我们发现 如果把dp[i-1]那一层直接拷贝到dp[i] 表达式就可以是：
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

压缩后的一维做法

 	int n, V;
    cin >> n >> V;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
    	for(int j = V; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + value[i]);
    cout << dp[V] << endl;

我们对01背包进行DP五部曲分析

1.确定dp数组的定义

在一维版的dp数组中，dp[j]代表当体积为j时，所背物品的最大价值

2.递推公式

dp[j] = max(dp[j],  dp[j - weight[i]] + value[j]);

3.对于数组的初始化

关于初始化我们要考虑到第1点和第2点，在实际问题中我们一般会把3和4联系在一起想

因为dp[j]表示：容量为j的背包，可以装下的最大价值是dp[j]

那么当j = 0 的时候什么也装不了 dp[0] = 0;

再来看到递推公式

因为dp数组的意义是最大价值那么当价值不为负的时候，非0下标初始化为0就可以了

但是当价值为负的时候，非0下标必须初始化到负无穷，不然初始值就会覆盖掉最大价值

//插 cpp如何把数组初始化成负无穷
memset(d, 0x8f, sizeof(d));

4.数组遍历的顺序

不同于一些线性DP的问题，背包问题在递推公式并没有直接给出递推的方向

for(int i = 1; i <= n; i++)
	for(int j = V; j >= w[i]; j--)
		dp[j] = max(dp[j], dp[j-w[i]] + value[i]);

这里我们突然发现滚动数组的遍历写法和二维数组的遍历写法有些不同

为什么内嵌循环的循环顺序是从大到小呢？

答：倒序遍历是因为保证每个物品只被放入背包一次

这里可能有些不太好理解

我们举一个例子：物品0重量w[0] = 1, value[0] = 15;

正序遍历：

dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30

物品0被加入了两次，怎么会是呢？

倒序遍历：

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15

从后往前遍历的话，每次取得的状态不会和之前取得的状态发生重叠，这样保证了每件物品加入一次

那么问题又来了，为什么二维数组中不需要倒序遍历呢?

因为二维数组中的dp[i] [j] 都是通过dp[i-1] [j]来得到的，本层的并不会被覆盖

此处较为拗口，建议实践出真知

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

达咩！

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

如果你不能理解的话，建议将for循环颠倒一下输出dp数组观察一下

5.举例推导

重量价值
物品0 1 15
物品1 3 20
物品2 4 30

一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下：

第一次遍历物品0 0 | 15 | 15 | 15 | 15

第二次遍历物品1 0 | 15 | 15 | 20 | 35

第三次遍历物品2 0 | 15 | 15 | 20 | 35

码农公寓