共计 5836 个字符,预计需要花费 15 分钟才能阅读完成。
你真的懂 01 背包问题吗?01 背包的这几问你能答出来吗?
对于 01 背包的几个问题
- 背包问题的动静转移方程是怎么来的?
- 你能解释背包问题的两个
for
循环的意义嘛? - 为什么须要两个
for
循环,一个循环行不行? - 01 背包问题的
for
循环肯定要从 0 开始吗? - 01 背包滚动数组的优化原理是什么?
- 01 背包只用不必二维数组只用一位数组的根据是什么?
这些问题在浏览完本文之后你将会失去答案!
01 背包问题介绍
有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能应用
一次
。第 $i$ 件物品的体积是 $v_i$,价值是 $w_i$。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
比方上面的 4 个物品,背包可能接受的最大分量为 5,咱们应该如何抉择,使得咱们取得的总价值最大:
物品 | 分量 | 价值 |
---|---|---|
A | 1 | 2 |
B | 2 | 4 |
C | 3 | 4 |
D | 4 | 5 |
这个问题还是比较简单,咱们间接看就晓得抉择物品 B 和物品 C 失去的价值最大。那么咱们如何设计一个算法去实现这个问题呢?首先对于每一个物品都有两种状况,抉择和不抉择,咱们须要抉择两种状况当中可能获取最大价值的那种状况。
01 背包问题动静转移方程
首先我么先要确定一个信息就是没件物品只有一件,选完就没有了。如果咱们的背包当中还有残余容量能够放下某个物品,那么对于这个物品咱们就有两种抉择:选
或者 不选
。
咱们定义数组 dp[i][j]
,其含意是对于前i
件物品,在咱们的背包容量为 j
的状况下咱们可能取得的最大的收益,如果咱们有 N
件物品,背包容量为 V
,那么咱们可能取得的最大价值为dp[N][V]
,因为他示意的是对于前N
个物品,在背包容量为 V
的状况下咱们可能获取到的最大的价值。咱们能够失去上面的公式:
$$
dp[i][j]=max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j]),如果背包的容量大于等于物品 i 占的体积
$$
$$
dp[i][j]=dp[i – 1][j],如果背包的容量小于物品 i 占的体积
$$
-
第一种状况(背包容量大于等于第
i
件物品的体积v[i]
时):- 在这种状况下咱们对于第
i
件物品有两种抉择,一种是将其放入背包当中,另外一种就是不选他,那么咱们就能够应用容量为j
的背包在前i-1
件物品进行抉择。 - 如果咱们选第
i
件物品,那么咱们背包剩下的容量就为j - v[i]
,咱们还能抉择的物品就是前i - 1
个物品,这个状况下可能取得的最大的收益为 $dp[i – 1][j – v[i]]$,再加上咱们抉择的第i
件物品的价值,咱们抉择第i
件物品可能取得的总收益为dp[i - 1][j - v[i]] + w[i]
。 - 如果咱们不抉择第
i
件物品,那么咱们背包残余容量依然为j
,而且咱们只能从前i - 1
个商品当中进行抉择,那么咱们最大的收益就为dp[i - 1][j]
。
- 在这种状况下咱们对于第
-
第二种状况(背包容量小于第
i
件物品的体积v[i]
时):- 这种状况下咱们只可能抉择前
i - 1
个商品,因而咱们可能获取的最大收益为dp[i - 1][j]
。
- 这种状况下咱们只可能抉择前
01 背包数据依赖问题剖析
在上文当中咱们曾经剖析进去了咱们的动静转移方程:
$$
dp[i][j]=max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j]),如果背包的容量大于等于物品 i 占的体积
$$
$$
dp[i][j]=dp[i – 1][j],如果背包的容量小于物品 i 占的体积
$$
依据下面两个公式剖析,咱们晓得要想解出 dp[i][j]
的值,咱们首先须要晓得 dp[i - 1][j - v[i]]
的值和 dp[i - 1][j]
的值,他们之间的依赖关系如下图所示:
基于下面的数据依赖关系,咱们晓得咱们如果想求 dp[N][V]
的值,首先要求出 dp
数组第 N - 1
行的所有的值,因为 dp[N][V]
依赖 dp[N - 1][V]
,而且可能依赖dp[N - 1][i]
的值(i
大于等于 0
,小于V
),而dp[N - 1][V]
又依赖dp[N - 2][]V
……
依据下面的剖析过程,如果咱们想计算出 dp[N][V]
的后果,那就须要从第 1
行开始往后计算,始终算到第 N
行,因而咱们能够写出上面的代码:
Java
版本:
import java.util.Scanner;
public class Main {public static int backpack(int[] w, int[] v, int N, int V) {int[][] dp = new int[N + 1][V + 1];
// 初始化
for (int i = v[1]; i <= V; ++i) {dp[1][i] = w[1];
}
// 第一行曾经初始化 从第二行开始
for (int i = 2; i <= N; ++i) {for (int j = 0; j <= V; ++j) {if (j >= v[i])
dp[i][j] = Math.max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[N][V];
}
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
int[] w = new int[N + 1];
int[] v = new int[N + 1];
for (int i = 1; i <= N; i++) {v[i] = scanner.nextInt();
w[i] = scanner.nextInt();}
System.out.println(backpack(w, v, N, V));
}
}
C++
版本:
#include <iostream>
using namespace std;
#define L 20000
int w[L]; // 物品价值
int v[L]; // 物品体积
int dp[L][L];
int N; // 物品数量
int V; // 背包的体积
int backpack() {
// 初始化
for (int i = v[1]; i <= V; ++i) {dp[1][i] = w[1];
}
// 第一行曾经初始化 从第二行开始
for (int i = 2; i <= N; ++i) {for (int j = 0; j <= V; ++j) {if (j >= v[i])
dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[N][V];
}
int main() {
cin >> N >> V;
for (int i = 1; i <= N; ++i) {cin >> v[i] >> w[i];
}
cout << backpack();
return 0;
}
从上图看咱们在计算第 i
的数据的时候咱们只依赖第 i - 1
行,咱们在第 i
行从后往前遍历并不会毁坏动静转移公式的要求。
因而上面的代码也是正确的:
public static int backpack(int[] w, int[] v, int N, int V) {int[][] dp = new int[N + 1][V + 1];
// 初始化
for (int i = v[1]; i <= V; ++i) {dp[1][i] = w[1];
}
// 第一行曾经初始化 从第二行开始
for (int i = 2; i <= N; ++i) {
// 这里是从开端到 0
// 后面是从 0 遍历到开端
for (int j = V; j >= 0; --j) {if (j >= v[i])
dp[i][j] = Math.max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[N][V];
}
01 背包问题优化——滚动数组
咱们在解决背包问的时候咱们是开拓了一个二维数组 dp
,那么咱们能不能想斐波拉契数列那样升高算法的空间复杂度呢?咱们曾经很分明了咱们在计算dp
数据的时候进行计算的时候只应用了两行数据,那么咱们只须要申请两行的空间即可,不须要申请那么大的数组空间,计算的时候重复在两行数据当中交替计算既可。比如说咱们曾经计算好第一行的数据了(初始化),那么咱们能够依据第一行失去的后果失去第二行,而后依据第二行,将计算的结后果从新存储到第一行,如此交替重复,像这种办法叫做 滚动数组
。
上面的代码当中 dp
数组是从第 0 行开始应用的,后面的代码是从第一行开始的。
import java.util.Scanner;
public class Main {public static int backpack(int[] v, int[] w, int V) {
int N = w.length;
int[][] dp = new int[2][V + 1];
for (int i = v[0]; i < V; ++i) {dp[0][i] = w[0];
}
for (int i = 1; i < N; ++i) {for (int j = V; j >= 0; --j) {if (j >= v[i])
dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j],
dp[(i - 1) % 2][j - v[i]] + w[i]);
else
dp[i % 2][j] = dp[(i - 1) % 2][j];
}
}
return dp[(N - 1) % 2][V];
}
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
int[] w = new int[N];
int[] v = new int[N];
for (int i = 0; i < N; i++) {v[i] = scanner.nextInt();
w[i] = scanner.nextInt();}
System.out.println(backpack(v, w, V));
}
}
背包空间再优化——单行数组和它的遍历程序问题
咱们还能持续压缩空间吗🤣?咱们在进行空间问题的优化的时候只有不毁坏动静转移公式,只须要咱们进行的优化可能满足 dp[i][j]
的计算在它所依赖的数据之后计算即可。
import java.util.Scanner;
public class Main {public static int backpack(int[] v, int[] w, int V) {
int N = w.length;
int[] dp = new int[V + 1];
for (int i = v[0]; i < V; ++i) {dp[i] = w[0];
}
for (int i = 1; i < N; ++i) {for (int j = V; j >= v[i]; --j) {dp[j] = Math.max(dp[j - v[i]] + w[i], dp[j]);
}
}
return dp[V];
}
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
int[] w = new int[N];
int[] v = new int[N];
for (int i = 0; i < N; i++) {v[i] = scanner.nextInt();
w[i] = scanner.nextInt();}
System.out.println(backpack(v, w, V));
}
}
咱们当初来好好剖析一下下面的代码:
- 依据动静转移公式
dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])
咱们晓得,第i
行的第j
个数据只依赖第i - 1
行的前j
个数据,跟第j
个数据之后的数据没有关系。因而咱们在应用一维数组的时候能够从后往前计算(且只能从后往前计算,如果从前往后计算会毁坏动静转移公式,因为第j
个数据跟他后面的数据有依赖关系,跟他前面的数据没有依赖关系)就可能满足咱们的动静转移公式。
- 如果咱们从在应用单行数组的时候从前往后计算,那么会使得一维数据后面局部数据的状态从
i - 1
行的状态变成第i
行的状态,像上面这样。
然而一维数组当中后局部的数据还是 i - 1
行的状态,当咱们去更新他们的时候他们依赖后面局部数据的 i - 1
行的状态,然而他们曾经更新到第 i
的状态了,因而毁坏了动静布局的转移方程,然而如果咱们从后往前进行遍历那么后面的状态始终是第 i - 1
行的状态,因而没有毁坏动静布局的转移方程,因而咱们须要从后往前遍历。
问题答案
如果你曾经看懂下面所议论到的内容的话,对于后面的几个问题置信你曾经有了答案。下面那些问题最终波及到的就是 01 背包问题的动静转移方程了,咱们在写代码的时候肯定不能毁坏动静转移方程,也就是要满足动静转移方程的依赖关系,即第 i
行的第 j
个数据只依赖第 i - 1
行的前 j
个数据,跟第 j
个数据之后的数据没有关系。
-
背包问题的两个
for
循环的意义:- 因为咱们须要解出
dp
数组当中第N
行第V
列的数据,所以咱们须要解出二维数组当中所有的数据,因而咱们须要进行二维数组的遍历,进行一维遍历不行。
- 因为咱们须要解出
-
01 背包问题的
for
循环肯定要从 0 开始吗?- 不肯定,咱们只须要满足动静转移方程的数据依赖要求就行,不论是从返回后还是从后往前咱们在应用二维
dp
数组的遍历的时候都能够满足数据依赖的要求。然而咱们如果应用一维数组的时候就肯定要从后往前遍历,因为如果从前往后遍历,第i
行状态会笼罩第i - 1
行的状态,而数组前面的数据须要i - 1
行状态的数据,而它有被笼罩了因而不行。
- 不肯定,咱们只须要满足动静转移方程的数据依赖要求就行,不论是从返回后还是从后往前咱们在应用二维
- 其余问题的答案在浏览完本文之后置信你心里曾经很分明了!!!
动静布局为什么叫动静布局
首先咱们须要明确什么是 布局
所谓的 布局
就是寻找最优值的过程,比如说咱们在旅行的时候做布局就是为了又更好旅行体验,而咱们在做算法题的时候须要找到最好的后果,比方在背包问题当中咱们要找到价值最大的一种抉择,这也是一种布局,那为什么是动静的呢?所谓动静就是咱们在寻找最优值的过程当中,抉择是变动的。比如说对于背包问题的公式 dp[i][j] = max(dp[i - 1][j - v[i] + w[i], dp[i - 1][j])
咱们在计算出后果之前并不知道那种抉择好,因为咱们要抉择两者两头值较大的哪个抉择,这就是动静抉择的过程!所以动静布局被称作动静布局!
总结
本篇文章次要带大家从 0 开始分析 01 背包问题,次要分享一些根本但常常被疏忽的问题,比方二重循环是如何被写进去的,for 循环的程序问题,数组空间优化问题的原理,用一维数组解决 01 背包问题!心愿大家有所播种,我是 LeHung,咱们下期再见!!!
更多精彩内容合集可拜访我的项目:https://github.com/Chang-LeHu…
关注公众号:一无是处的钻研僧,理解更多计算机(Java、Python、计算机系统根底、算法与数据结构)常识。