我需要维基百科的一些澄清：背包，部分
因此，该解决方案将在O（nW）时间和O（nW）空间中运行。另外，如果我们仅使用一维数组m [W]来存储当前的最优值并经过该数组i + 1次，每次从m [W]重写为m [1]，我们将得到相同的结果仅O（W）空间。
我无法理解如何将2D矩阵转换为1D矩阵以节省空间。另外，这rewriting from m[W] to m[1] every time意味着什么（或它如何工作）。
rewriting from m[W] to m[1] every time
请提供一些示例。假设我的集合{V，W}-> {（5,4），（6,5），（3,2）}且K = 9。
一维阵列的外观如何？
在许多动态编程问题中，您将逐行构建一个2D表，其中每行仅取决于其紧前面的行。如果是0/1背包问题，则重复发生的次数（来自Wikipedia）如下：
如果w i > w ，则m [i，w] = m [i-1，w] m [i，w] = max（m [i-1，w]，m [i-1，w-w i ] + v i）否则
如果w i > w ，则m [i，w] = m [i-1，w]
m [i，w] = max（m [i-1，w]，m [i-1，w-w i ] + v i）否则
注意，当填充第i行时，所有从表中读取的数据仅来自第i-1行；表格中较早的行实际上并未使用。因此，您可以通过仅存储两行来节省2D表中的空间- 紧接的前一行和您要填充的行。您可以通过更加智能的填写方式来进一步将其优化为仅一行表条目。这样可以将空间使用量从O（nW）（O（n）行和O（W）列）减少到O（W）（一两行和O（W）列）。
不过，这是有代价的。许多DP算法并不会在运行时显式计算解决方案，而是填写表格，然后在表格最后进行第二遍操作以恢复最佳答案。如果只存储一行，那么您将获得最佳答案的 值 ，但是您可能不知道最佳答案是什么。在这种情况下，您可以读取可放入背包的最大值，但不一定能够恢复要获得的最大价值。
希望这可以帮助！
