a

发表于 | 分类于

01 背包

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

  • 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
  • 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int knapsack(int W, int N, int[] weights, int[] values) {
    int[][] dp = new int[N + 1][W + 1];
    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] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N][W];
}

在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，

img

因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，以防将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。

  • 第一重循环枚举物品。
  • 第二重循环枚举容量（倒序枚举）。
  • 时间复杂度为 O(NW)。
1
2
3
4
5
6
7
8
9
10
public int knapsack(int W, int N, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    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] = Math.max(dp[j], dp[j - w] + v);
        }
    }
    return dp[W];
}

注意 dp 数组初始化方式（对于其他背包问题也适用）：

  • 不超过容量时，全都初始化为 0，即dp[i] = 0 (i=0,1,...)，结果为 dp[W]。
  • 恰好等于容量时，dp[0] 初始化为 0，其余初始化为无穷大（可能是正无穷，也可能是负无穷，视情况而定），即 dp[0] = 0；dp[i] = INF (i=1,...)，结果为 dp[W]。

完全背包

01 背包是每个物品要么选 0 次，要么 1 次。而完全背包每个物品可以选择无数多次，只要满足条件即可。

  • 第一重循环枚举物品。
  • 第二重循环枚举容量（正序枚举）。
  • 时间复杂度为 O(NW)。
1
2
3
4
5
6
7
8
9
10
public int knapsack(int W, int N, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    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] = Math.max(dp[j], dp[j - w] + v);
        }
    }
    return dp[W];
}

多重背包

每个物品体积为 w，价值为 v，有 s 个。多重背包为每个物品增加了一个数量属性，每个物品可以选。是 01 背包问题的拓展，可以转化为 01 背包问题。状态转移方程为

dp[j] = max{dp[j], dp[j - w] + v, dp[j - 2 * w] + 2 * v, ..., dp[j - s * w] + s * v}。

  • 第一重循环枚举物品。
  • 第二重循环枚举容量（倒序枚举）。
  • 第三重循环枚举数量（决策）。
  • 时间复杂度为 O(NWS)。
1
2
3
4
5
6
7
8
9
10
11
public int knapsack(int W, int N, int[] weights, int[] values, int[] ss) {
    int[] dp = new int[W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1], s = ss[i];
        for (int j = W; j >= w; j--) {
            for (int k = 1; k <= s && k * w <= j; ++k)
            dp[j] = Math.max(dp[j], dp[j - k * w] + k * v);
        }
    }
    return dp[W];
}

优化方式一：二进制拆分。

  • 把数量 s 拆分成 1、2、4、8、…。若 s 不是 2 的幂减一，则最后一个数为 s 与前面所有拆分数之和的差。拆分得到数可以组成 1~s 范围内的所有数。
    • 例如 7 拆分成 1、2、4，这三个数可以组成 1~7 范围内的所有数。
    • 例如 10 拆分成 1、2、4、3，这四个数可以组成 1~10 范围内的所有数。
  • 用拆分的数重新形成物品，这样多重背包就转化为了 01 背包。
  • 第一重循环枚举物品。
  • 第二重循环枚举容量（倒序枚举）。
  • 时间复杂度为 O(NWlogS)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int knapsack(int W, int N, int[] weights, int[] values, int[] ss) {
    int[] dp = new int[W + 1];
    List<Data> list = new ArrayList<>();
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1], s = ss[i];
        for (int k = 1; k <= s; k <<= 1) {
            s -= k;
            list.add(new Data(k * w, k * v));
        }
        if (s > 0) {
            list.add(new Data(s * w, s * v));
        }
    }
    for (Data data : list) {
        for (int j = W; j >= data.w; --j) {
            dp[j] = Math.max(dp[j], dp[j - data.w] + data.v);
        }
    }
    return dp[W];
}

class Data {
    int w, v;

    public Data(int w, int v) {
        this.w = w;
        this.v = v;
    }
}

优化方式二：单调队列。

待写。

混合背包

物品一共有三类：

  • 第一类物品只能用1次（01背包）；si = −1 表示第 i 种物品只能用 1 次。
  • 第二类物品可以用无限次（完全背包）；si = 0 表示第 i 种物品可以用无限次。
  • 第三类物品最多只能用 si 次（多重背包）；si > 0 表示第 i 种物品可以用 si 次。

把多重背包按照二进制拆分拆成 01 背包，这样就只有 01 背包和完全背包，分别按照 01 背包和完全背包方式解决即可（一个倒序、一个正序）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public int knapsack(int W, int N, int[] weights, int[] values, int[] ss) {
    int[] dp = new int[W + 1];
    List<Data> list = new ArrayList<>();
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1], s = ss[i];
        if (s <= 0) {
            list.add(new Data(w, v, s));
        } else {
            // 多重背包进行二进制拆分
            for (int k = 1; k <= s; k <<= 1) {
                s -= k;
                list.add(new Data(k * w, k * v, -1));
            }
            if (s > 0) {
                list.add(new Data(s * w, s * v, -1));
            }
        }
    }
    for (Data data : list) {
        if (data.s < 0) { // 01 背包
            for (int j = W; j >= data.w; --j) {
                dp[j] = Math.max(dp[j], dp[j - data.w] + data.v);
            }
        } else {		  // 完全背包
            for (int j = data.w; j <= W; ++j) {
                dp[j] = Math.max(dp[j], dp[j - data.w] + data.v);
            }
        }
    }
    return dp[W];
}

class Data {
    int w, v, s;

    public Data(int w, int v, int s) {
        this.w = w;
        this.v = v;
        this.s = s;
    }
}

二维费用背包

之前讨论的背包问题限制条件只有一个，是一维的。可以有不止一个，即多维费用背包。以二维费用背包为例，还多了一个条件，不能超过总重量 M。

  • 第一重循环枚举物品。
  • 第二重循环枚举容量（倒序枚举）。
  • 第二重循环枚举重量（倒序枚举）。
1
2
3
4
5
6
7
8
9
10
11
12
public int knapsack(int W, int N, int M, int[] weights, int[] mm, int[] values) {
    int[][] dp = new int[W + 1][M + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1], m = mm[i - 1];
        for (int j = W; j >= w; j--) {
            for (int k = M; k >= m; --k) {
                dp[j][k] = Math.max(dp[j][k], dp[j - w][k - m]);
            }
        }
    }
    return dp[W];
}

分组背包

有 N 组物品，每组物品由若干个（假设为 s），同一组内的物品最多只能选一个。状态转移方程为

dp[j] = max{dp[j], dp[j - w[0]] + v[0], dp[j - w[1]] + v[1], ..., dp[j - w[s - 1]] + v[s - 1]}。

与多重背包进行对比，多重背包选择 1 个、2个、3个…，这些可以构成一组。

可以看出，多重背包是分组背包的一种特殊形式，所以多重背包可以进行优化。

  • 第一重循环枚举物品。
  • 第二重循环枚举容量（倒序枚举）。
  • 第三重循环枚举当前组（决策）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int knapsack(int W, int N, int[][] w, int[][] v) {
    int[][] dp = new int[W + 1][M + 1];
    for (int i = 1; i <= N; i++) {
        int s = weights[i].length;
        for (int j = W; j >= 0; j--) {
            for (int k = 0; k < s; ++k) {
                if (j >= w[k]) {
                    dp[j] = Math.max(dp[j], dp[j - w[k]] + v[k]);
                }
            }
        }
    }
    return dp[W];
}

总结

  • 背包问题解决方案都是第一重循环物品，第二重循环费用（可能有多重），第三重循环决策（可能没有循环）。
  • 01 背包第一重循环物品，第二重循环费用，倒序枚举。
  • 完全背包第一重循环物品，第二重循环费用，正序枚举。
  • 很多其他背包问题是 01 背包或完全背包的变种，可以转化为 01 背包或完全背包来解决。
  • dp 数组初始化时，全部初始化为 0 表示不超过总费用，除了 dp[0] 外其余初始化为正无穷或负无穷表示恰好为总费用。