## 01背包问题 C++ 实现
简介
01背包问题是经典的动态规划问题之一。问题描述如下：给定一个容量为 `W` 的背包和 `n` 个物品，每个物品有其重量 `weight[i]` 和价值 `value[i]`。目标是选择一些物品放入背包，使得背包内物品的总重量不超过 `W`，且总价值最大。每个物品只能选择放入或不放入，因此称为 01 背包。### 1. 问题分析与状态转移方程解决 01 背包问题可以使用动态规划。我们定义状态 `dp[i][j]` 表示考虑前 `i` 个物品，背包容量为 `j` 时所能获得的最大价值。状态转移方程如下：
不放入第 `i` 个物品:
`dp[i][j] = dp[i-1][j]`
放入第 `i` 个物品 (前提是背包容量足够):
`dp[i][j] = dp[i-1][j - weight[i]] + value[i]`最终结果为 `dp[n][W]`。### 2. C++ 代码实现 (二维数组)```cpp
#include
#include
#include using namespace std;int knapsack01_2D(int W, int n, vector& weight, vector& value) {vector> dp(n + 1, vector(W + 1, 0));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= W; ++j) {if (j < weight[i - 1]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);}}}return dp[n][W];
}int main() {int W = 10;int n = 4;vector weight = {2, 3, 5, 7};vector value = {1, 5, 2, 4};int maxValue = knapsack01_2D(W, n, weight, value);cout << "Max Value: " << maxValue << endl; // Output: 9return 0;
}
```### 3. C++ 代码实现 (一维数组优化)二维数组的解法可以优化为一维数组，从而降低空间复杂度。需要注意的是，内层循环 `j` 必须从 `W` 倒序遍历到 `weight[i-1]`，以避免覆盖之前的结果。```cpp
#include
#include
#include using namespace std;int knapsack01_1D(int W, int n, vector& weight, vector& value) {vector dp(W + 1, 0);for (int i = 1; i <= n; ++i) {for (int j = W; j >= weight[i - 1]; --j) {dp[j] = max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);}}return dp[W];
}int main() {int W = 10;int n = 4;vector weight = {2, 3, 5, 7};vector value = {1, 5, 2, 4};int maxValue = knapsack01_1D(W, n, weight, value);cout << "Max Value: " << maxValue << endl; // Output: 9return 0;
}
```### 4. 总结01背包问题是动态规划的入门问题，理解其状态转移方程是关键。通过二维数组和一维数组两种实现方式，可以更好地理解动态规划的思想和优化技巧。一维数组的实现方式在空间复杂度上更优，实际应用中更常用。希望这篇文章能够帮助你理解和掌握 01 背包问题的 C++ 实现。
01背包问题 C++ 实现**简介**01背包问题是经典的动态规划问题之一。问题描述如下：给定一个容量为 `W` 的背包和 `n` 个物品，每个物品有其重量 `weight[i]` 和价值 `value[i]`。目标是选择一些物品放入背包，使得背包内物品的总重量不超过 `W`，且总价值最大。每个物品只能选择放入或不放入，因此称为 01 背包。
1. 问题分析与状态转移方程解决 01 背包问题可以使用动态规划。我们定义状态 `dp[i][j]` 表示考虑前 `i` 个物品，背包容量为 `j` 时所能获得的最大价值。状态转移方程如下：* **不放入第 `i` 个物品:** `dp[i][j] = dp[i-1][j]`
* **放入第 `i` 个物品 (前提是背包容量足够):** `dp[i][j] = dp[i-1][j - weight[i]] + value[i]`最终结果为 `dp[n][W]`。
2. C++ 代码实现 (二维数组)```cpp
include
include
include using namespace std;int knapsack01_2D(int W, int n, vector& weight, vector& value) {vector> dp(n + 1, vector(W + 1, 0));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= W; ++j) {if (j < weight[i - 1]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);}}}return dp[n][W];
}int main() {int W = 10;int n = 4;vector weight = {2, 3, 5, 7};vector value = {1, 5, 2, 4};int maxValue = knapsack01_2D(W, n, weight, value);cout << "Max Value: " << maxValue << endl; // Output: 9return 0;
}
```
3. C++ 代码实现 (一维数组优化)二维数组的解法可以优化为一维数组，从而降低空间复杂度。需要注意的是，内层循环 `j` 必须从 `W` 倒序遍历到 `weight[i-1]`，以避免覆盖之前的结果。```cpp
include
include
include using namespace std;int knapsack01_1D(int W, int n, vector& weight, vector& value) {vector dp(W + 1, 0);for (int i = 1; i <= n; ++i) {for (int j = W; j >= weight[i - 1]; --j) {dp[j] = max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);}}return dp[W];
}int main() {int W = 10;int n = 4;vector weight = {2, 3, 5, 7};vector value = {1, 5, 2, 4};int maxValue = knapsack01_1D(W, n, weight, value);cout << "Max Value: " << maxValue << endl; // Output: 9return 0;
}
```
4. 总结01背包问题是动态规划的入门问题，理解其状态转移方程是关键。通过二维数组和一维数组两种实现方式，可以更好地理解动态规划的思想和优化技巧。一维数组的实现方式在空间复杂度上更优，实际应用中更常用。希望这篇文章能够帮助你理解和掌握 01 背包问题的 C++ 实现。
引导者
