[雜記] 01背包記錄路徑

眾所周知，01背包的時間復雜度是\(O(nm)\)（n為物品數量，m為背包容量），空間復雜度是\(O(m)\)。如果還需要輸出最優解中的所有物品的話，時間復雜度不變，空間復雜度呢？

你的第一反應可能是：我很快就可以給出一個空間復雜度也是\(O(m)\)的算法啊？

但實際上這個算法是有問題的：

int n;		// 物品數量
int m;		// 背包容量
int w[N];	// 物品重量
int v[N];	// 物品價值
int dp[M];	// dp數組
int pre[M];	// 路徑

void package01() {
    for (int i = 1; i <= n; i ++) {
        for (int j = m; j >= w[i]; j --) {
            if (dp[j] < dp[j-w[i]] + v[i]) {
                dp[j] = dp[j-w[i]] + v[i];
                pre[j] = i;
            }
        }
    }

    int j = m;
    while (pre[j] != 0) {
        int last = pre[j];
        printf("%d, ", last);
        j -= w[last];
    }
}

這樣寫有什么問題呢？

當然有！

比如對于下面的樣例：

n = 3;
m = 4;
w[] = {1, 1, 2};
v[] = {1, 1, 4};

輸出結果就是

3, 3,

第三個物品被用了兩次。

這時你可能恍然大悟，因為在第三個物品加入后，pre[2]被更新為了3，所以就丟失了前兩個物品的路徑。

本質原因在于，一開始的01背包本來就是二維數組\(dp[i][j]\)，表示“只使用前i個物品，背包容量為j時的最大價值”，這時\(pre[i][j]\)的意義就是“只使用前i個物品，背包容量為j，達到最大價值時最后一個購買的物品”。轉移是：

if (dp[i-1][j] > dp[i-1][j-w[i]] + v[i]) {
	dp[i][j] = dp[i-1][j-w[i]] + v[i];
	pre[i][j] = i;
}
else {
	dp[i][j] = dp[i-1][j];
	pre[i][j] = pre[i-1][j];
}

路徑是：

int i = n, j = m;
while (pre[i][j] != 0) {
    int last = pre[i][j];
    printf("%d, ", last);
    i = last - 1; 
    j -= w[last];
}

如果把pre壓縮為1維，相當于最后只剩下\(pre[n][.]\)，前面\(pre[<n][.]\)的路徑信息就丟失了，這樣就沒法輸出完整路徑了。

那有沒有時間復雜度還是\(O(nm)\)，空間復雜度低于\(O(nm)\)的做法呢？

好吧我是沒想出來。

不過倒是有一種能讓空間降低32倍的做法：將pre變成一個01數組，\(pre[i][j]=1\)表示“只使用前i個物品，背包容量為j，達到最大價值時最后一個購買的物品就是i”。這樣也能輸出完整的路徑。

int i = n, j = m;
while (i != 0) {
    while (!pre[i][j])
        i --;
    printf("%d, ", i);
    j -= w[i];
    i --;
}

如果有高人能給出空間復雜度低于\(O(nm)\)的做法，歡迎交流。