学 0-1 背包学了不知道多久，可算给我把一维滚动数组的解法研究明白了。qwq
问题
有 NNN 个物品，给定其价值与质量，其中第 iii 个物品的价值与质量分别记作 DiD_iDi 与 WiW_iWi 。现在要从这些物品中选取若干个（每个物品只能选一次）并放入一个背包，要求这些物品的质量之和不能超过背包的最大容量 MMM。求能取到的最大价值和。
思路
考虑到 O(2n)\mathcal{O}(2^n)O(2n) 的时间复杂度，尝试枚举每一种选择方案找最大值并不是什么好主意。贪心无法取得全局最优解，而模拟退火相信就算我会也懒得写。因此该问题的较简便实用正解应该是使用动态规划。
定义 dpi,jdp_{i,j}dpi,j 表示从前 iii 个物品里挑选且背包容量为 jjj 时可取到的最大价值。显然，若背包可用容量不够取当前物品，则只能不取当前物品并继承上一个物品的最大价值；否则最大价值就是取与不取的情况的最大值。
即本题的二维状态转移方程为
dpi,j={dpi−1,j,j<Wimax(dpi−1,j,dpi−1,j−Wi+Di),j≥Widp_{i,j}= \begin{cases} dp_{i-1,j},&j<W_i\\ \max(dp_{i-1,j},dp_{i-1,j-W_i}+D_i),&j\geq W_i \end{cases} dpi,j ={dpi−1,j ,max(dpi−1,j ,dpi−1,j−Wi +Di ), j<Wi j≥Wi
在初始值上，当背包容量为 000 或物品数为 000 时，很显然总价值也为 000，于是 dpi,0dp_{i,0}dpi,0 ，dp0,idp_{0,i}dp0,i 的初始值皆为 000。我们可以写出如下解法：
时间复杂度：O(N⋅W)\mathcal{O}(N \cdot W)O(N⋅W)
空间复杂度：O(N⋅W)\mathcal{O}(N \cdot W)O(N⋅W)
但是，若数据范围太大了，这种解法会 MLE。
考虑优化。我们可以让dp[][]改用short类型，但这治标不治本，若数据范围再大一些一样无法通过，某些情况下还有溢出的风险。
我们发现，在原本的状态转移方程中，dpi,jdp_{i,j}dpi,j 都是从 dpi−1,xdp_{i-1,x}dpi−1,x 转移而来的，存储 dpi−2,xdp_{i-2,x}dpi−2,x 等其他维度并的数据并不必要。于是我们可以考虑使用一维滚动数组直接省去 iii 这个维度。
时间复杂度：O(N⋅W)\mathcal{O}(N \cdot W)O(N⋅W)
空间复杂度：O(W)\mathcal{O}(W)O(W)
解释一下滚动数组究竟是怎么处理这些数据的。每次 i←i+1i \leftarrow i+1i←i+1 的时候，当前要处理的是第 i+1i+1i+1 个物品的选择，而dp[]数组里存的恰好是用于转移的处理完上一个物品的数据（也就是第 iii 个物品），于是直接用数组中已有的数据转移即可，不再需要额外存储。
为了解释为什么 jjj 要从高到低遍历，我们首先要知道，j-weights[i]的值永远不会大于当前的 jjj。从高到低遍历时，已经转移的部分在 jjj 之上，由于j-weights[i]的值在 jjj 之下，dp[j-weights[i]]不会访问到已经转移过的部分，保证了其永远是未转移后的上一轮的状态；从低到高遍历，则此时已经转移的部分都在 jjj 以下，又因为j-weights[i]的值的范围，就会访问到已经转移的部分，进而出现错误。
注意，如果需要给出选择方案，一维滚动数组的解法会比较麻烦，建议使用二维数组的解法。
