用动态规划解决0-1背包问题（给定n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W，求最大总价值），请说明状态转移方程、时间复杂度，并举例说明如何应用。
信步科技研发难度：中等
答案
1) 【一句话结论】：0-1背包问题通过动态规划定义状态dp[i][j]（前i个物品装容量j的最大价值），状态转移为dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，时间复杂度为O(nW)，适用于物品不可分割的背包问题。
2) 【原理/概念讲解】：动态规划解决0-1背包的核心是“状态定义+状态转移+边界条件”。
- 状态定义：设
dp[i][j]表示前i个物品（物品1到物品i）装入容量为j的背包所获得的最大价值。 - 状态转移：对于第i个物品，有两种选择——
- 不选：价值为前i-1个物品装容量j的最大价值，即
dp[i-1][j]； - 选择：此时背包剩余容量为
j-w[i]，价值为前i-1个物品装容量j-w[i]的最大价值加上当前物品价值，即dp[i-1][j-w[i]] + v[i]；
取两者最大值作为dp[i][j]。
- 不选：价值为前i-1个物品装容量j的最大价值，即
- 边界条件：
- 无物品时：
dp[0][j]=0（无论背包容量多大，价值为0）； - 背包容量为0时：
dp[i][0]=0（无论有多少物品，价值为0）。
类比：购物时每个商品（物品）要么买（选）要么不买（不选），背包容量限制商品总重量，动态规划通过记录每个“选择状态”下的最优解，避免重复计算。
- 无物品时：
3) 【对比与适用场景】：
| 模型 | 0-1背包 | 完全背包 |
|---|---|---|
| 定义 | 每个物品仅能使用1次，不可分割 | 每个物品可无限使用，不可分割 |
| 状态转移 | dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) | dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) |
| 时间复杂度 | O(nW) | O(nW)（内层循环从0到j-w[i]） |
| 适用场景 | 珠宝、书籍、电子产品（不可重复使用） | 糖果、饮料（可重复购买） |
| 注意点 | 确保物品索引和容量索引正确，避免越界 | 内层循环方向影响计算顺序（通常从0到j-w[i]） |
4) 【示例】：
假设有3个物品，重量w=[2,3,4]，价值v=[3,4,5]，背包容量W=5。
- 初始化：
dp[0][j]=0（所有j），dp[i][0]=0（所有i）。 - 遍历物品1（重量2，价值3）：
j=2时，dp[1][2]=max(0, dp[0][2]+3)=3（选物品1）。 - 遍历物品2（重量3，价值4）：
j=5时，dp[2][5]=max(dp[1][5], dp[1][2]+4)=max(0, 3+4)=7（选物品1和物品2，重量2+3=5，价值3+4=7）。 - 遍历物品3（重量4，价值5）：
j=5时，dp[3][5]=max(dp[2][5], dp[2][1]+5)=max(7, 0)=7（最终最大价值为7）。
5) 【面试口播版答案】：
“0-1背包问题用动态规划解决，核心是定义状态dp[i][j]表示前i个物品装进容量为j的背包的最大价值。状态转移方程是dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中i从1到n，j从0到W。边界条件是dp[0][j]=0（0个物品时，任何容量价值为0），dp[i][0]=0（容量为0时，任何物品价值为0）。时间复杂度是O(nW)，因为双重循环遍历物品和容量。举个例子，物品重量[2,3,4]，价值[3,4,5]，容量5，通过状态转移计算得到最大价值为7（选物品1和物品2，重量2+3=5，价值3+4=7），这就是0-1背包问题的解法。”
6) 【追问清单】：
- 问：为什么每个物品只能用一次？
答：因为0-1背包问题中物品不可分割，每个只能选或不选，状态转移中考虑选或不选，避免重复使用。 - 问：时间复杂度为什么是O(nW)？
答：外层循环遍历物品（n次），内层循环遍历容量（W次），总操作次数为n*W，故时间复杂度为O(nW)。 - 问：空间是否可以优化？
答：可以，用一维数组dp[j]表示当前容量下的最大价值，因为当前状态只依赖上一行（前i-1个物品），空间复杂度可降为O(W)。 - 问：边界条件是否正确？
答：是的，dp[0][j]=0（无物品时，任何容量价值为0），dp[i][0]=0（容量为0时，任何物品价值为0），确保初始状态正确。 - 问：如何处理物品数量或容量较大的情况？
答：对于大数，用long long存储避免溢出；若n或W很大，可考虑近似算法（如贪心或动态规划优化），但核心状态转移不变。
7) 【常见坑/雷区】：
- 状态定义错误：将
dp[i][j]误解为“i个物品装j的”，转移时索引混乱，导致计算错误。 - 边界条件遗漏：忘记初始化
dp[0][j]或dp[i][0]，导致结果错误。 - 转移方程索引越界：如
j-w[i] < 0时未判断，导致数组访问错误。 - 时间复杂度计算错误：误以为O(n²)或O(W²)，实际是O(nW)。
- 物品顺序影响：0-1背包中物品顺序不影响最终结果，但计算时需正确遍历每个物品，避免遗漏。