0/1背包动态编程Optimazion,从2D矩阵到1D矩阵

Question

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

因此,该解决方案将在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.

一维阵列怎么样？

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
第二种方法也是2D,但只使用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
第三种方法使用1D表.

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

Answer 2

在许多动态编程问题中，您将逐行构建一个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）否则

请注意，填充第i行时，所有从表中读取的数据仅来自第i-1行；表中较早的行实际上并未使用。因此，您可以通过仅存储两行来节省2D表中的空间-紧接的前一行和您要填充的行。您可以通过更加智能的填写方式来进一步将其优化为仅一行表条目。这样可以将空间使用量从O（nW）（O（n）行和O（W）列）减少到O（W）（一两行和O（W）列）。

不过，这是有代价的。许多DP算法并不会在运行时显式计算解决方案，而是填写表格，然后在表格最后进行第二遍操作以恢复最佳答案。如果仅存储一行，那么您将获得最佳答案的值，但是您可能不知道最佳答案是什么。在这种情况下，您可以读取适合背包的最大值，但不一定能够恢复要达到的最大价值。

希望这可以帮助！