11

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

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

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

一维数组会是什么样子？

4

3 回答 3

28

我知道这是一个老问题。但是我不得不花一些时间来寻找这个，我只是在这里记录这些方法以供任何人将来参考。

方法 1
使用 N 行的直接 2D 方法是：

int dp[MAXN][MAXW];
int solve()
{
    memset(dp[0], 0, sizeof(dp[0]));
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j <= W; j++) {
            dp[i][j] = (w[i] > j) ? dp[i-1][j] : max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
        }
    }
    return dp[N][W];
}

这使用 O(NW) 空间。

方法 2
您可能会注意到，在计算特定行的矩阵条目时，我们只查看前一行而不是之前的行。这可以被利用来仅维护 2 行并保持将它们的角色交换为当前行和上一行。

int dp[2][MAXW];
int solve()
{
    memset(dp[0], 0, sizeof(dp[0]));
    for(int i = 1; i <= N; i++) {
        int *cur = dp[i&1], *prev = dp[!(i&1)];
        for(int j = 0; j <= W; j++) {
            cur[j] = (w[i] > j) ? prev[j] : max(prev[j], prev[j-w[i]] + v[i]);
        }
    }
    return dp[N&1][W];
}

这需要 O(2W) = O(W) 空间。cur是第 i 行，prev是第 (i-1) 行。
方法 3
如果再看一遍，您会发现，当我们在一行中写入一个条目时，我们只查看了上一行中左侧的项目。我们可以使用它来使用单行并从右到左处理它，这样当我们为一个条目计算新值时，它左边的条目具有它们的旧值。这是一维表方法。

int dp[MAXW];
int solve()
{
    memset(dp, 0, sizeof(dp));
    for(int i =1; i <= N; i++) {
        for(int j = W; j >= 0; j--) {
            dp[j] = (w[i] > j) ? dp[j]: max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    return dp[W];
}

这也使用 O(W) 空间，但只使用单行。必须反转内循环的主要原因是因为当我们使用 时dp[j-w[i]]，我们需要外循环上一次迭代的值。为此，j必须以从大到小的方式处理这些值。

测试用例（来自http://www.spoj.com/problems/PARTY/）

N = 10, W = 50
w[] = {0, 12, 15, 16, 16, 10, 21, 18, 12, 17, 18} // 1 based indexing
v[] = {0, 3, 8, 9, 6, 2, 9, 4, 4, 8, 9}

答案 = 26

于 2014-10-12T12:58:39.887 回答
12

在许多动态规划问题中，您将逐行构建一个 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 算法不会在执行过程中明确计算解决方案，而是填写表格，然后在最后对表格进行第二次遍历以恢复最佳答案。如果您只存储一行，那么您将获得最佳答案的值，但您可能不知道最佳答案是什么。在这种情况下，您可以读出可以装入背包的最大值，但不一定能够恢复为达到该值而应该做的事情。

希望这可以帮助！

于 2013-06-22T02:21:35.743 回答
0

回答您的问题：如果我们对数组使用基于 0 的索引，那么编写递归关系的正确方法是：

dp[i][j] = (w[i-1] > j) ? dp[i-1][j] : max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);

由于i表示第 1i项，例如如果i是 5，则第 5 项将分别位于 weights 和 values 数组中的第 4 位，因此wt[i-1]和v[i-1]。

于 2021-11-26T05:02:18.867 回答