01背包问题与普通背包问题在实际应用中常被混淆,但两者在约束条件和解法上有明显差异。以下是它们的主要区别总结:
| 对比项 | 01背包问题 | 普通背包问题 |
| 物品选择 | 每个物品只能选一次 | 每个物品可选多次 |
| 状态转移方程 | dp[i] = max(dp[i], dp[i - w] + v) | dp[i] = max(dp[i], dp[i - w] + v) |
| 时间复杂度 | O(n C) | O(n C) |
| 应用场景 | 资源有限且不可重复使用 | 资源可重复使用 |
01背包强调“不可重复选取”,而普通背包允许物品多次选取。理解两者的区别有助于在实际问题中选择合适的算法模型。