涉及题目
01 背包二维：46. 携带研究材料（第六期模拟笔试）
01 背包一维：46. 携带研究材料（第六期模拟笔试）
分割等和子集：416. 分割等和子集 - 力扣（LeetCode）
解题步骤
确定 dp 数组（dp table）以及下标的含义 确定递推公式 dp 数组如何初始化 确定遍历顺序 举例推导 dp 数组
01 背包二维
思路
第一步：
dp[i][j] 及其下标 i、j 的含义
dp[i][j] 表示：考虑前 i+1 个物品（第 0i 个物品），在背包容量为 j 时，能装入的物品的最大价值；
下标 i：对应物品的索引（0m-1），表示'处理到第几个物品'；
下标 j：对应背包的容量（0~n），表示'当前背包的剩余容量'；
举例：dp[2][5] 表示考虑前 3 个物品（0、1、2 号），背包容量为 5 时的最大价值。
第二步：
确定状态转移方程 0-1 背包的核心规则是'每个物品只能选或不选'，因此对于第 i 个物品，有两种选择： 情况 1：不选第 i 个物品 此时背包容量不变，最大价值继承'考虑前 i 个物品（0~i-1）、容量 j'的结果 → dp[i][j] = dp[i-1][j]； 触发条件：j < weight[i]（背包容量不足，装不下第 i 个物品，只能不选）。
情况 2：选第 i 个物品 此时背包容量减少 weight[i]，价值增加 value[i]，最大价值 = '考虑前 i 个物品、容量 j-weight[i] 的价值' + value[i] → dp[i-1][j - weight[i]] + value[i]； 触发条件：j >= weight[i]（容量足够，可选）。
第三步：
dp 数组如何初始化 初始化需贴合'无物品 / 无容量'的边界场景，保证后续计算的基准正确： 容量为 0 时（j=0）：无论有多少物品，背包容量为 0 都装不了任何物品，价值为 0 → dp[i][0] = 0（所有行的第 0 列都为 0）； 只有第一个物品时（i=0）： 若 j < weight[0]：装不下第一个物品，价值为 0（数组默认值，无需显式赋值）； 若 j >= weight[0]：只能装第一个物品，价值为 value[0] → dp[0][j] = value[0]； 补充：数组默认值为 0，因此 j < weight[0] 的位置无需额外赋值，只需处理 j >= weight[0] 的情况。
第四步：
外层循环（物品）：从 i=1 到 m-1（第一个物品已初始化），因为 dp[i][j] 依赖 dp[i-1][j]（上一行的结果），需按物品顺序遍历； 内层循环（容量）：从 j=0 到 n，遍历所有可能的背包容量，因为每个容量的状态都需要基于上一行的结果计算； 核心原则：先遍历物品，再遍历容量（0-1 背包二维 DP 的固定顺序，保证每个物品只被考虑一次）。
二维数组处理的 01 背包问题实际上先遍历容量再遍历物品也是可以的。
第五步：
输入：m=2（2 个物品），n=5（背包容量 5）； 重量：weight = [1, 3]，价值：value = [2, 4]； 初始化 容量为 0：dp[0][0] = 0，dp[1][0] = 0； 第一个物品（i=0）： j >= 1 时，dp[0][j] = 2 → dp[0] = [0,2,2,2,2,2]； 计算第二个物品（i=1） j=0：dp[1][0] = 0； j=1：j < 3 → dp[1][1] = dp[0][1] = 2； j=2：j < 3 → dp[1][2] = dp[0][2] = 2； j=3：j >=3 → max(dp[0][3]=2, dp[0][0]+4=4) → dp[1][3] =4； j=4：j >=3 → max(dp[0][4]=2, dp[0][1]+4=6) → dp[1][4] =6； j=5：j >=3 → max(dp[0][5]=2, dp[0][2]+4=6) → dp[1][5] =6； 最终结果 dp[1][5] =6（装第一个 + 第二个物品，总价值 2+4=6），符合最优解。
实现代码
import java.util.*;
import java.lang.*;
public class Main {
public static void main(String[] args) {
Scanner (System.in);
sc.nextInt();
sc.nextInt();
[][] dp = [m][n + ];
[] weight = [m];
[] value = [m];
( ; i < m; i++) {
weight[i] = sc.nextInt();
}
( ; i < m; i++) {
value[i] = sc.nextInt();
}
( ; i < m; i++) {
dp[i][] = ;
}
( weight[]; j <= n; j++) {
dp[][j] = value[];
}
( ; i < m; i++) {
( ; j <= n; j++) {
(j < weight[i]) {
dp[i][j] = dp[i - ][j];
} {
dp[i][j] = Math.max(dp[i - ][j], dp[i - ][j - weight[i]] + value[i]);
}
}
}
System.out.println(dp[m - ][n]);
sc.close();
}
}
