从2维矩阵到1维矩阵的0/1背包动态规划优化 [英] 0/1 Knapsack Dynamic Programming Optimization, from 2D matrix to 1D matrix

问题描述

我需要从维基百科得到一些澄清：Knapsack，关于

因此，该解将在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意味着什么(或它是如何工作的)。

请举一些例子。假设我有集合{V，W}-->{(5，4)，(6，5)，(3，2)}，K=9。

一维阵列的外观如何？

推荐答案

在许多动态编程问题中，您将逐行构建2D表，其中每行只依赖于其前面的行。在0/1背包问题的情况下，递归(来自维基百科)如下：

m[i，w]=m[i-1，w]，如果w_i>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算法在执行过程中不显式地计算解，而是填写表格，然后在结束时对表格进行第二次遍历，以恢复最优解。如果只存储一行，那么您将获得最佳答案的值，但您可能不知道该最佳答案是什么。在这种情况下，您可以读出背包中可以容纳的最大值，但您不一定能够恢复为实现该值而应该执行的操作。

希望这能有所帮助！

这篇关于从2维矩阵到1维矩阵的0/1背包动态规划优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！