0-1背包问题非递归算法详解：如何计算最大价值与空间优化技巧

0-1背包问题非递归算法详解：如何计算最大价值与空间优化技巧

0-1背包算法是一个非常经典的算法问题。可惜我一直只知道它的递归算法。今天刚学了非递归算法。我就记录在这里。

定义一个二维数组 maxValues[ ][ ] 记录最大值。 maxValues[i][V]表示从前i个物品中选择物品放入容量为V的背包中可以获得的最大值，则有方程 maxValues[i][V] = max{ maxValues[i-1][V], maxValues[i-1][V-ws[i]] +values[i] } （其中ws[i]表示第i个项目占用的空间，values[i] ] 代表的值第 i 项），让我们解释一下这个方程：

每个物品只有两个选择：放入背包或不放入背包。在考虑是否放入第i项时，如果选择放入，则可以获得的值就是第i项的值加上剩余空间。在i-1项中选择时可以获得的最大值，如果选择不放入，则获得的值是在现有空间中选择i-1项时可以获得的最大值。显然，我们必须选择最有价值的一个。

我们再优化一下。如果我们查看二维数组 maxValues，我们可以发现 maxValues[i-1][y] 仅在计算 maxValues[i][x] (y