什么是背包问题？
● 简单来说就是：一个小偷背了一个背包潜进了金店，包就那么大，他如果保证他背出来所有物品加起来的价值最大。
● 规范描述就是：有一个容量为 W 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v 。
背包问题分类:
最常见的背包问题有0-1背包，完全背包，多重背包，分组背包这四种：
● 按照每个物品的数量分类。
● 其中最重要的是 0 - 1背包 和 完全背包 。
0 - 1背包
问题描述：一个最多能背体积为 W 的背包 和 n 件物品。第 i 件物品的体积是 weight ，价值是 value 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
解题思路：
定义一个二维数组 dp 存储最大价值，其中 dp[j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。
设第 i 件物品体积为 w[i]，价值为 v，根据第 i 件物品 是否添加 到背包中，可以分两种情况讨论：
1. 第 i 件物品 没添加 到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i -1 件物品的最大价值，dp[j] = dp[i-1][j]。
2. 第 i 件物品 添加 到背包中，dp[j] = dp[i-1][j-w] + v。
第 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[j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
} else {
dp[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[j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
} else {
dp[j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
空间优化
在程序实现时可以对 0 - 1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i - 1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[j]。此时，
因为要使用 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[j-w]，防止将 dp[i-1][j-w] 覆盖。
也就是说要先计算 dp[j] 再计算 dp[j-w]，在程序实现时需要按 倒序 来循环求解。
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[j] 表示在前 i 个物品中，背包容量为 j 时能够获得的最大价值。
动态规划的状态转移公式如下：
● 其中 w 表示第 i 个物品的重量，v 表示第 i 个物品的价值。
● 第一项 dp[i-1][j] 表示 不选择 第 i 个物品;
● 第二项 dp[j-w] + v 表示 选择 第 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[j] = Math.max(dp[i - 1][j], dp[j - weights[i - 1]] + values[i - 1]);
} else {
dp[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[j] = Math.max(dp[i - 1][j], dp[j - weights[i - 1]] + values[i - 1]);
} else {
dp[j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
和 0 - 1 背包类似，可以优化空间复杂度为一维数组，使用 dp[j] 表示背包容量为 j 时的最大价值。状态转移公式为：
和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.
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的;
只需记住：动规是由前一个状态推导出来的，而贪心是局部直接选最优的。
————————————————
本文转载自CSDN平台博主酷酷的懒虫
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_43412762/article/details/129485663
完善个人信息