Leetcode 日记：背包问题

Leetcode 日记：背包问题

四月 01, 2022

背包问题

背包问题是一种组合优化的NP 完全问题：有N 个物品和容量为W 的背包，每个物品都有
自己的体积w 和价值v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物
品只能选择0 个或1 个，则问题称为0-1 背包问题；如果不限定每种物品的数量，则问题称为无
界背包问题或完全背包问题。

我们可以用动态规划来解决背包问题。以0-1 背包问题为例。我们可以定义一个二维数组dp
存储最大价值，其中dp[i][j] 表示前i 件物品体积不超过j 的情况下能达到的最大价值。在我们遍
历到第i 件物品时，在当前背包总容量为j 的情况下，如果我们不将物品i 放入背包，那么dp[i][j]
= dp[i-1][j]，即前i 个物品的最大价值等于只取前i-1 个物品时的最大价值；如果我们将物品i 放
入背包，假设第i 件物品体积为w，价值为v，那么我们得到dp[i][j] = dp[i-1][j-w] + v。我们只需在遍历过程中对这两种情况取最大值即可，总时间复杂度和空间复杂度都为O(NW)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int knapsack(vector<int> weights, vector<int> values, int N, int W){
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for(int i = 1; i <= N; ++i){
        int w = weights[i-1], v = values[i-1];
        for(int j = 1; j <= W; ++j){
            if(j >= w){
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
            }
            else{
                dp[i][j] = dp[i-1][j];
            }        
        }
    }
    return dp[N][W];
}

bb1

我们可以进一步对0-1 背包进行空间优化，将空间复杂度降低为O(W)。如图所示，假设我们目前考虑物品i = 2，且其体积为w = 2，价值为v = 3；对于背包容量j，我们可以得到dp[2][j] = max(dp[1][j], dp[1][j-2] + 3)。这里可以发现我们永远只依赖于上一排i = 1 的信息，之前算过的其他物品都不需要再使用。因此我们可以去掉dp 矩阵的第一个维度，在考虑物品i 时变成dp[j] = max(dp[j], dp[j-w] + v)。这里要注意我们在遍历每一行的时候必须逆向遍历，这样才能够调用上一行物品i-1 时dp[j-w] 的值；若按照从左往右的顺序进行正向遍历，则dp[j-w] 的值在遍历到 j 之前就已经被更新成物品i 的值了。

1
2
3
4
5
6
7
8
9
10
11
int knapsack(vector<int> weights, vector<int> values, int N, int W){
    vector<int> dp(W + 1, 0);
    for(int i = 1; i <= N; ++i){
        int w = weights[i-1], v = values[i-1];
        for(int j = W; j >= w; --j){
            dp[j] = max(dp[j], dp[j-w] + v);
        }
    }
    return dp[W];
}

bb2

在完全背包问题中，一个物品可以拿多次。如图上半部分所示，假设我们遍历到物品i = 2，
且其体积为w = 2，价值为v = 3；对于背包容量j = 5，最多只能装下2 个该物品。那么我们的状
态转移方程就变成了dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)。如果采用这种方法，假设
背包容量无穷大而物体的体积无穷小，我们这里的比较次数也会趋近于无穷大，远超O(NW)的
时间复杂度。
怎么解决这个问题呢？我们发现在dp[2][3] 的时候我们其实已经考虑了dp[1][3] 和dp[2][1]
的情况，而在时dp[2][1] 也已经考虑了dp[1][1] 的情况。因此，如图下半部分所示，对于拿多个
物品的情况，我们只需考虑dp[2][3] 即可，即dp[2][5] = max(dp[1][5], dp[2][3] + 3)。这样，我们
就得到了完全背包问题的状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)，其与0-1 背包问
题的差别仅仅是把状态转移方程中的第二个i-1 变成了i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int knapsack(vector<int> weights, vector<int> values, int N, int W){
    vector<vector<int>> dp(N+1, vector<int>(W+1, 0));
    for(int i = 1; i <= N; ++i){
        int w = weights[i-1], v = velues[i-1];
        for(int j = 1; j <= W; ++j){
            if(j >= w){
                dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[N][W];

}

同样的，我们也可以利用空间压缩将时间复杂度降低为O(W)。这里要注意我们在遍历每一
行的时候必须正向遍历，因为我们需要利用当前物品在第j-w 列的信息。

1
2
3
4
5
6
7
8
9
10
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = w; j <= W; ++j) {
            dp[j] = max(dp[j], dp[j-w] + v);
        }
    }
    return dp[W];
}