背包问题是指给定一组物品，每种物品都有对应的重量和价值，在限定总重量的情况下，选择物品使得总价值最大的一类优化问题，其中0-1背包是最基础也最常见的变种，每个物品只能选择放入背包一次或者完全不放入。
0-1背包问题的核心逻辑
使用动态规划解决0-1背包问题，首先需要明确状态定义和状态转移方程。
状态定义
我们定义dp[i][j]表示前i个物品，在背包容量为j的情况下能获得的最大价值。其中i的取值范围是0到物品总数n，j的取值范围是0到背包最大容量W。
状态转移方程
对于第i个物品（重量w，价值v），有两种选择：
- 不放入背包：此时最大价值等于前i-1个物品在容量j下的最大价值，即
dp[i][j] = dp[i-1][j] - 放入背包：前提是当前容量j大于等于物品重量w，此时最大价值等于前i-1个物品在容量j-w下的最大价值加上当前物品价值v，即
dp[i][j] = dp[i-1][j-w] + v
最终状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)，当j < w时只能选择不放入。
基础二维数组实现方案
按照上述状态定义和转移方程，我们可以写出基础的二维数组实现代码，完整示例如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
// 定义dp数组，初始化为0
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
// 遍历所有物品
for (int i = 1; i <= n; i++) {
int w = weights[i-1];
int v = values[i-1];
// 遍历所有容量
for (int j = 0; j <= capacity; j++) {
// 当前容量放不下第i个物品，只能不放入
if (j < w) {
dp[i][j] = dp[i-1][j];
} else {
// 选择放入或不放入，取最大值
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v);
}
}
}
// 返回最终最大价值
return dp[n][capacity];
}
int main() {
// 物品重量数组
vector<int> weights = {2, 3, 4, 5};
// 物品价值数组
vector<int> values = {3, 4, 5, 6};
// 背包最大容量
int capacity = 8;
int maxValue = knapsack01(weights, values, capacity);
cout << "背包能装下的最大价值为：" << maxValue << endl;
return 0;
}
上述代码中，我们先初始化了一个(n+1)*(capacity+1)的二维数组，然后双重循环遍历所有物品和容量，按照转移方程填充dp数组，最终返回dp[n][capacity]就是最大价值。这种实现的时间复杂度是O(n*W)，空间复杂度也是O(n*W)。
空间优化的一维数组实现
观察二维数组的转移过程可以发现，dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w]，也就是上一行的状态，因此我们可以把二维数组优化为一维数组，减少空间占用。
优化时需要注意，遍历容量的顺序必须从大到小，避免同一物品被重复放入背包。完整代码示例如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack01_optimized(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
// 定义一维dp数组，初始化为0
vector<int> dp(capacity + 1, 0);
// 遍历所有物品
for (int i = 0; i < n; i++) {
int w = weights[i];
int v = values[i];
// 容量从大到小遍历，避免重复放入
for (int j = capacity; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
return dp[capacity];
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
int capacity = 8;
int maxValue = knapsack01_optimized(weights, values, capacity);
cout << "优化后背包能装下的最大价值为：" << maxValue << endl;
return 0;
}
优化后的代码空间复杂度降到了O(W)，时间复杂度仍然保持O(n*W)，在处理大规模数据时能有效减少内存占用。
常见问题说明
很多开发者在写一维数组实现时容易搞错容量遍历顺序，这里需要特别注意：如果容量从小到大遍历，那么dp[j-w]已经是当前轮次更新过的状态，相当于同一个物品可以被多次放入，就变成了完全背包问题的逻辑，不符合0-1背包的要求。只有从大到小遍历，才能保证dp[j-w]是上一轮的状态，每个物品只被考虑一次。
另外如果物品重量或者价值有负数，上述逻辑需要做对应调整，实际开发中需要根据具体的问题约束修改状态转移的条件。