0/1背包动态规划Optimazion，从二维矩阵维矩阵 [英] 0/1 Knapsack Dynamic Programming Optimazion, from 2D matrix to 1D matrix

问题描述

我需要从维基百科一些澄清：背包，对部分

I need some clarification from wikipedia: Knapsack, on the part

因此​​，该解决方案将运行在O（NW）时间和O（NW）的空间。此外，如果   我们仅使用1维阵列米[W]以存储当前的最优值   而过这阵我+ 1次，从M [W] [1]每一次改写为M，我们   获取仅O（W）的空间中的相同的结果。

This solution will therefore run in O(nW) time and O(nW) space. Additionally, if we use only a 1-dimensional array m[W] to store the current optimal values and pass over this array i+1 times, rewriting from m[W] to m[1] every time, we get the same result for only O(W) space.

我无法理解如何将一个二维矩阵成一维矩阵，以节省空间。此外，为了什么呢从M [W]改写为米[1]每次平均值（或它如何工作）。

I am having trouble understanding how to turn a 2D matrix into a 1D matrix to save space. In addition, to what does rewriting from m[W] to m[1] every time mean (or how does it work).

请提供一些例子。说如果我有集合{V，W} - > {（5,4），（6,5），（3,2）}与K = 9。

Please provide some example. Say if I have the set {V,W} --> {(5,4),(6,5),(3,2)} with K = 9.

如何将一维数组什么样子的？

How would the 1D array look like?

推荐答案

在许多动态编程的问题，你将建立一个二维表一行一行的每行仅依赖立即precedes它的行上。在0/1背包问题的情况下，复发（维基百科）如下：

In many dynamic programming problems, you will build up a 2D table row by row where each row only depends on the row that immediately precedes it. In the case of the 0/1 knapsack problem, the recurrence (from Wikipedia) is the following:

M [I，W = M [ - 1，W]当w <子>我>是W

m[i, w] = m[i - 1, w] if w_i > w

M [I，W = MAX（M [ - 1，W]，M [ - 1，W - 含<子>我] + V <子>我）否则

m[i, w] = max(m[i - 1, w], m[i - 1, w - w_i] + v_i) otherwise

请注意，从表中填行我只能来自行我当所有的读取 - 1;在表中的较早的行没有实际使用。因此，你可以保存的二维表空间只能存放两行 - 在马上previous行，你填写该行可以通过是有点聪明关于如何进一步优化这个下降到只有一行您填写的表项。这降低了O（NW）（O（n）的行和O（W）列）的空间使用，以O（W）（一行或两行和O（W）列）。

Notice that all reads from the table when filling row i only come from row i - 1; the earlier rows in the table aren't actually used. Consequently, you could save space in the 2D table by only storing two rows - the immediately previous row and the row you're filling in. You can further optimize this down to just one row by being a bit more clever about how you fill in the table entries. This reduces the space usage from O(nW) (O(n) rows and O(W) columns) to O(W) (one or two rows and O(W) columns).

这是有代​​价的，虽然。许多DP算法不明确计算的解决方案，因为他们去，而是填写表格，然后做第二次传过来的表底，以恢复最佳的答案。如果你只存储一个行，那么你将得到的值的最佳答案，但你可能不知道什么是最佳的答案恰好是。在这种情况下，你可以读出，你可以放入背包中的最大值，但你也不一定能够恢复什么你应该做的，为了实现这一价值。

This comes at a cost, though. Many DP algorithms don't explicitly compute solutions as they go, but instead fill in the table, then do a second pass over the table at the end to recover the optimal answer. If you only store one row, then you will get the value of the optimal answer, but you might not know what that optimal answer happens to be. In this case, you could read off the maximum value that you can fit into the knapsack, but you won't necessarily be able to recover what you're supposed to do in order to achieve that value.

希望这有助于！

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