背包模板

发表于 | 更新于 | 分类于 ， ，
本文字数： 6.1k

  01背包模板，复杂度\(O(V*N)\)

1
2
3
4
​for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

  一个常数优化如下 

1
2
3
4
5
6
for (int i = 1; i <= n; i++) {
    int bound = max(V - sum{w[i]...w[n]}, v[i]);
    for (int j = V; j >= bound, j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);
}

  完全背包模板，复杂度\(O(V*N)\)

1
2
3
4
for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= V; j++)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

  二进制拆分多重背包模板，复杂度\(O(V*\sum log(p[i]))\)

1
2
3
4
5
6
7
8
9
for (int i = 1; i <= n; i++) {
    int num = min(number[i], V / w[i]);
    for (int k = 1; num > 0; k <<= 1) {
        if (k > num) k = num;
        num -= k;
        for (int j = V; j >= w[i] * k; j--)
            f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
    }
}

  单调队列优化多重背包模板，复杂度\(O(V*N)\)，外层还需要嵌套一个\(1...n\)的循环

1
2
3
4
5
6
7
8
9
10
11
12
13
//p：某类物品数量，w：某类物品花费，v：某类物品价值，V:商品总价值
void MultiPack(int p, int w, int v) {
    for (int j = 0; j < w; j++) { //j为w的所有组
        int head = 1, tail = 0;
        for (int k = j, i = 0; k <= V / 2; k += w, i++) {
            int r = f[k] - i * v;
            while (head <= tail and r >= q[tail].v) tail--;
            q[++tail] = node(i, r);
            while (q[head].id < i - p) head++; //需要的物品数目
            f[k] = q[head].v + i * v;
        }
    }
}