0/1背包动态规划优化，从二维矩阵到一维矩阵

Question

我需要从维基百科上得到一些澄清：背包问题，具体在以下部分中：

这个解决方案将以O(nW)时间和O(nW)空间运行。此外，如果我们只使用一个一维数组m[W]来存储当前最优值，并且在每次重写时将其传递i + 1次，从m[W]重写到m[1]，那么我们将仅使用O(W)空间获得相同的结果。

我不理解如何将2D矩阵转换为1D矩阵以节省空间。此外，“每次将从m[W]重写到m[1]”是什么意思（或者它是如何工作的）。

请提供一些示例。比如我有一个集合{V,W} --> {(5,4),(6,5),(3,2)}，K = 9.

一维数组会长成什么样子？

- Jack

Answer 1

我知道这是一个老问题。但是我不得不花费一些时间搜索，现在我将记录这些方法以供将来参考。

方法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

- avmohan

---

对于方法3，我们只需要将j减少到w[i]而不是0，然后我们就可以得到for(int j = W; j >= w[i]; --j) dp[j] = max(dp[j], dp[j-w[i]] + v[i]);。 - Peter Lee

内部循环必须被反转，因为当我们使用dp[j-w[i]]时，我们需要来自外部循环的上一次迭代的值。您能解释一下这是为什么吗？ - Trajan

@permian 你可以比较一下 method1 和 method3 中如何计算循环。在一维数组中的 dp[j]（method1）应该对应于二维数组中的 dp[i-1][j]（method3），而不是 dp[i][j]，也就是说，我们需要从 i 循环的上一次迭代中获取 dp[j] 的值，而不是当前迭代。 此外，请注意，由于所有的 w[i] 都是正数，所以 j-w[i] < j，即我们只从正在写入的左侧槽位读取，从右侧槽位不读取。我们可以利用这一点将行数从 2 行减少到 1 行，同时仍然能够通过反转 j 循环来读取 i 循环的前一次迭代的值。 - avmohan

Answer 2

在许多动态规划问题中，您将按行构建一个二维表格，其中每一行仅依赖于紧接在其前面的行。在 0/1 背包问题的情况下，递归式（来自维基百科）如下：

如果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 行；实际上没有使用表格中的早期行。因此，您可以通过仅存储两行（即直接前一行和正在填充的行）来节省二维表格中的空间。通过更聪明地填充表格条目，您可以进一步将其优化为只有一行。这将将空间使用量从 O(nW)（O(n) 行和 O(W) 列）降低到 O(W)（一个或两个行和 O(W) 列）。

但是，这是有代价的。许多 DP 算法不会随着计算而显式地计算解，而是填充表格，然后在最后对表格进行第二次遍历以恢复最优解。如果您只存储一行，则将得到最优答案的值，但您可能不知道该最优答案是什么。在这种情况下，您可以读取适合背包的最大值，但您不一定能够恢复为了实现该值而应执行的操作。

希望对您有所帮助！

- templatetypedef

---

针对我的情况，我需要记住选择了哪个条目，并根据您的说法，我不一定能够恢复我实现该值的方式；这是否意味着我不能将 O(n*W) 转换为 O(W) 以解决这个特定问题？ - Jack

换句话说，优化空间使用仅适用于我们不需要记住选择了哪些项目，只想知道最大值的情况下吗？ - Jack

@templatetypedef，您能帮忙解释一下为什么一维解决方案需要从m[w]迭代到m[j]，为什么不能从m[j]迭代到m[w]？ - Peiti Li

如果我们从左到右迭代，它将覆盖先前 i 的较小权重的值。 - avmohan

Answer 3

回答你的问题：如果我们对数组使用从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表示前i个项目，例如如果i为5，则第5个项目将位于权重和价值数组中的第4个位置，因此分别为wt[i-1]和v[i-1]。

- Sriram Krishnamurthy