1. 01 背包（每种物品只能选一次）
思路：
每个物品只能取 0 次或 1 次，求在容量限制内的最大价值。
定义
dp[j]表示容量j时的最大价值。遍历物品，从后向前遍历容量，防止物品被重复使用。
状态转移方程：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
代码模板：
for (int i = 0; i < N; i++) { // 遍历物品
for (int j = V; j >= w[i]; j--) { // 倒序遍历背包容量
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
示例： 输入：
3 5
2 3
1 2
3 4
计算过程：
初始化
dp = [0, 0, 0, 0, 0, 0]。处理第一个物品（重量2，价值3）：
dp[5] = max(dp[5], dp[3] + 3) = 3dp[4] = max(dp[4], dp[2] + 3) = 3dp[3] = max(dp[3], dp[1] + 3) = 3dp[2] = max(dp[2], dp[0] + 3) = 3
处理第二个物品（重量1，价值2），依次更新。
处理第三个物品（重量3，价值4），依次更新。
最终 dp[5] = 5。
2. 完全背包（每种物品可以选无限次）
思路：
每个物品可以取无限次。
仍然定义
dp[j]，但这次要正序遍历容量。状态转移方程：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
代码模板：
for (int i = 0; i < N; i++) { // 遍历物品
for (int j = w[i]; j <= V; j++) { // 正序遍历背包容量
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
示例： 输入：
2 4
1 2
2 4
计算过程：
初始化
dp = [0, 0, 0, 0, 0]。处理第一个物品（重量1，价值2）：
dp[1] = 2, dp[2] = 4, dp[3] = 6, dp[4] = 8
处理第二个物品（重量2，价值4）：
dp[2] = 4（不变），dp[3] = 6（不变），dp[4] = 8（不变）
最终 dp[4] = 8。
3. 多重背包（每种物品最多选 Si 次）
思路：
直接按照 01 背包 方式处理的时间复杂度较高。
使用 二进制拆分优化，将
s[i]个物品拆分成若干个2^k份，使得2^0 + 2^1 + ...覆盖s[i]。状态转移方程：
dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i])
代码模板（使用二进制优化）：
for (int i = 0; i < N; i++) { // 遍历物品
int count = s[i];
for (int k = 1; count > 0; k *= 2) { // 二进制拆分
int num = Math.min(k, count);
count -= num;
int weight = num * w[i];
int value = num * v[i];
for (int j = V; j >= weight; j--) { // 01 背包处理
dp[j] = Math.max(dp[j], dp[j - weight] + value);
}
}
}
示例： 输入：
3 10
2 3 3
3 4 2
5 6 2
计算过程（使用二进制优化拆分）：
物品1（重量2，价值3，最多选3次）拆分成
1, 2：dp[10] = max(dp[10], dp[8] + 3)dp[8] = max(dp[8], dp[6] + 3)依次更新
dp[2] = 3, dp[4] = 6, dp[6] = 9
物品2（重量3，价值4，最多选2次）拆分成
1, 1：依次更新
dp[3] = 4, dp[6] = 8, dp[9] = 12
物品3（重量5，价值6，最多选2次）拆分成
1, 1：dp[5] = 6, dp[10] = 12
最终 dp[10] = 12。
总结：
01 背包： 只能选 0 或 1 次，倒序遍历容量。
完全背包： 可选无限次，正序遍历容量。
多重背包： 每种物品最多选
Si次，二进制拆分优化。