Java中0-1背包问题的空间优化DP解决方案
内容提要
本文介绍了Java中0-1背包问题的空间优化动态规划解决方案，通过减少额外空间的使用来计算背包问题的最优解。背包问题是一个组合优化问题，目标是选择物品使得总重量小于容量且总价值最大。背包问题在现实生活中有多种应用。
延伸解读
空间优化核心：为何一维数组可行
传统二维DP需要O(n*W)空间存储所有状态，但计算dp[i][cap]时只依赖上一行dp[i-1][cap]和dp[i-1][cap-wt[i]]。因此可用一维数组prev滚动更新，将空间降至O(W)。关键点在于内层循环必须从W到0逆序遍历，确保计算cap时用到的prev[cap-wt[i]]仍是上一轮（即未放入当前物品）的值，避免同一物品被重复放入。
实现细节：初始化与边界处理
代码中先初始化prev数组：对于容量i从wt[0]到W，prev[i] = val[0]，表示只考虑第一个物品时的最大价值。随后从第二个物品开始迭代，内层逆序遍历容量。当wt[i] > cap时，taken设为Integer.MIN_VALUE，表示无法放入，此时只能选择不拿。最终返回prev[W]即为答案。这种初始化方式简洁，但需注意物品重量可能大于容量，循环起始点要正确。
复杂度与适用场景
该算法时间复杂度为O(n*W)，辅助空间O(W)。相比二维DP，空间大幅减少，适合W较大但n适中的场景。但若W极大（如10^9），O(W)空间仍不可行，此时需考虑其他方法。此外，该优化不改变时间效率，仅节省内存，因此适用于内存受限但时间可接受的场合。
Q&A
0-1背包问题是什么？
0-1背包问题是一个组合优化问题：给定N个物品，每个物品有重量wi和价值vi，以及一个容量为W的背包，目标是选择物品放入背包，使得总重量不超过W且总价值最大。每件物品只能选择放入或不放入，不能分割。
背包问题有哪些常见类型？
背包问题主要分为四类：分数背包问题（允许分解物品）、0/1背包问题（每件物品只能选或不选）、有界背包问题（每种物品有数量限制）、无界背包问题（每种物品可无限选择）。
0-1背包问题的空间优化DP是如何实现的？
空间优化DP使用一维数组prev来存储前一行的最大值。初始化prev数组后，遍历每个物品，对于每个容量从W到0逆序遍历，计算不选当前物品（prev[cap]）和选当前物品（val[i] + prev[cap - wt[i]]）的最大值，更新prev[cap]。最终prev[W]即为最大价值。
空间优化DP的时间复杂度和空间复杂度是多少？
时间复杂度为O(n * W)，其中n是物品数量，W是背包容量；辅助空间复杂度为O(W)，因为只使用了一个长度为W+1的一维数组。
背包问题在现实生活中有哪些应用？
背包问题在现实生活中有多种应用，例如：考试构建和评分（考生选择回答哪些问题）、子集和问题、运输物流优化（多目标变体）、运筹学中的装载和调度算法（多背包问题）等。
0-1背包问题与分数背包问题有什么区别？
0-1背包问题要求每件物品只能完全放入或不放入，不能分割；而分数背包问题允许将物品分解，可以取物品的一部分，以最大化总价值。
