什么是背包问题？
- 简单来说就是：一个小偷背了一个背包潜进了金店，包就那么大，他如果保证他背出来所有物品加起来的价值最大。
- 规范描述就是：有一个容量为
W的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积w和价值v。
背包问题分类:
最常见的背包问题有0-1背包，完全背包，多重背包，分组背包这四种：
- 按照每个物品的数量分类。
- 其中最重要的是 0 - 1背包 和 完全背包 。
0 - 1背包
问题描述：一个最多能背体积为
W的背包 和n件物品。第i件物品的体积是weight[i]，价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
解题思路：
定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。
设第 i 件物品体积为 w[i]，价值为 v[i]，根据第 i 件物品 是否添加 到背包中，可以分两种情况讨论：
- 第
i件物品 没添加 到背包，总体积不超过j的前i件物品的最大价值就是总体积不超过j的前i -1件物品的最大价值，dp[i][j] = dp[i-1][j]。 - 第
i件物品 添加 到背包中，dp[i][j] = dp[i-1][j-w[i]] + v[i]。
第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0 -1 背包的状态转移公式为：
d
p
[
i
]
[
j
]
=
max
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
w
[
i
]
]
+
v
[
i
]
)
d p[i][j]=\max (dp[i-1][j], dp[i-1][j-w[i]]+v[i])
dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])
万能统一代码：(Java、C++)
Java:
// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
C++ :
// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
int knapsack(int W, int N, vector<int> weights, vector<int> values) {
vector<vector<int>> dp(N + 1, vector<int>(W + 1));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {
if (j >= weights[i - 1]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
空间优化
在程序实现时可以对 0 - 1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i - 1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，
d
p
[
j
]
=
max
(
d
p
[
j
]
,
d
p
[
j
−
w
[
i
]
]
+
v
[
i
]
)
d p[j]=\max (dp[j], dp[j-w[i]]+v[i])
dp[j]=max(dp[j],dp[j−w[i]]+v[i])
因为要使用 dp[j-w[i]] 表示 dp[i-1][j-w[i]]，因此不能先求 dp[i][j-w[i]]，防止将 dp[i-1][j-w[i]] 覆盖。
也就是说要先计算 dp[i][j] 再计算 dp[i][j-w[i]]，在程序实现时需要按 倒序 来循环求解。
Java:
public int knapsack(int W, int N, int[] weights, int[] values) {
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
for (int j = W; j >= 1; j--) {
if (j >= weights[i - 1]) {
dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[W];
}
C++:
int knapsack(int W, int N, vector<int> weights, vector<int> values) {
vector<int> dp(W + 1);
for (int i = 1; i <= N; i++) {
for (int j = W; j >= 1; j--) {
if (j >= weights[i - 1]) {
dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[W];
}
完全背包
与 0 - 1 背包问题相似，但在完全背包问题中，物品的数量是无限的，可以选择任意多个相同的物品放入背包。
解题思路：
和 0 - 1 背包类似，我们可以定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时能够获得的最大价值。
动态规划的状态转移公式如下：
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
]
[
j
−
w
[
i
]
]
+
v
[
i
]
)
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])
dp[i][j]=max(dp[i−1][j],dp[i][j−w[i]]+v[i])
- 其中
w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。 - 第一项
dp[i-1][j]表示 不选择 第i个物品; - 第二项
dp[i][j-w[i]] + v[i]表示 选择 第i个物品（可能不止一个，和0-1背包相区别！）。
万能统一代码：(Java、C++)
Java:
// W 为背包总体积
// N 为物品的种类
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
C++ :
// W 为背包总体积
// N 为物品的种类
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
int knapsack(int W, int N, vector<int> weights, vector<int> values) {
vector<vector<int>> dp(N + 1, vector<int>(W + 1));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
空间优化
- 和 0 - 1 背包类似，可以优化空间复杂度为一维数组，使用
dp[j]表示背包容量为j时的最大价值。状态转移公式为：
d p [ j ] = m a x ( d p [ j ] , d p [ j − w [ i ] ] + v [ i ] ) dp[j] = max(dp[j], dp[j-w[i]] + v[i]) dp[j]=max(dp[j],dp[j−w[i]]+v[i])
和0-1背包不同，在程序实现时按 正序 来循环求解。
Java:
public int knapsack(int W, int N, int[] weights, int[] values) {
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {
if (weights[i - 1] <= j) {
dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[W];
}
C++:
int knapsack(int W, int N, vector<int> weights, vector<int> values) {
vector<int> dp(W + 1);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {
if (weights[i - 1] <= j) {
dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[W];
}
无法使用贪心算法的解释
0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。
考虑下面的物品和一个容量为 5 的背包:
- 如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。
- 最优的方式是存放物品 1 和物品 2，价值为 22.
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的;
只需记住：动规是由前一个状态推导出来的，而贪心是局部直接选最优的。
LeetCode题目 —— 实战 ！！！：
416. 分割等和子集
494. 目标和
474. 一和零
322. 零钱兑换
518. 零钱兑换 II
139.单词拆分
377. 组合总和 Ⅳ
1049. 最后一块石头的重量 II 文章来源：https://www.toymoban.com/news/detail-449917.html
注：仅供学习参考!文章来源地址https://www.toymoban.com/news/detail-449917.html
到了这里，关于一篇文章吃透背包问题！！！【动态规划】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
