背包九讲

发表于 | 分类于 | | 热度: ℃

以下是学习背包九讲的学习笔记，只有前八讲。原文链接。

01背包问题

Description

有 $n$ 件物品，一个容量为 $m$ 的背包。每个物品有价值 $v$ 和重量 $w$。挑选一些物品放入背包，每个物品只能用一次，求最大价值。

Solution

做法1

设 $f[i][j]$ 为当前到第 $i$ 个物品，已经用 $j$ 容量的最大价值。

转移方程：$f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])$

以上做法的时间、空间复杂度均为 $O(nm)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int v[200], w[200], n, m, f[2000][2000], ans = 0;
int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j - v[i] >= 0)
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
        }
    for(int i = 1; i <= m; i++) ans = max(ans, f[n][i]);
    printf("%d", ans);
    return 0;
}

优化1

时间复杂度难以优化，但可以优化空间复杂度到 $O(m)$。设 $f[i]$ 为表示容量为 $i$ 的背包能够得到的最大价值。

转移方程：$f[i]=max(f[i],f[i-w[i]]+v[i])$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, v[200], w[200], f[2000];
int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    printf("%d", f[m]);
    return 0;
}

完全背包问题

Description

还是 $01$ 背包问题，但不同的是每个物品可以用无限次。

Solution

做法1

还是设 $f[i][j]$ 为当前到第 $i$ 个物品，已经用 $j$ 容量的最大价值。

每次在循环内枚举 $k$ 作为当前物品使用的次数。直到当前容量再也无法放开为止。

可以看出这种做法的时空复杂度都很高。（因为在 $oj$ 上爆内存，所以下面的代码没有经过测试）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, ans = 0, v[200], w[200], f[200][2000];
int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for(int k = 1; j >= k * w[i]; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - w[i] * k] + v[i] * k);
        }
    for(int i = 0; i <= m; i++)	ans = max(ans, f[n][i]);
    printf("%d", ans);
    return 0;
}

优化1

先不考虑压缩空间，先来优化一下时间复杂度。之前 $i$ 这一层是由 $i-1$ 这一层更新来的，现在我们用 $i$ 这一层来平级地更新自己。会意一下，发现 $k$ 这一层不用循环了。（代码还是没有测试）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, ans = 0, v[20000], w[20000], f[2000][2000];
int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= w[i])
            	f[i][j] = max(f[i][j], f[i][j - w[i]] + v[i]);
        }
    for(int i = 0; i <= m; i++)	ans = max(ans, f[n][i]);
    printf("%d", ans);
    return 0;
}

优化2

先来明确一下优化后的 $01$ 背包 $j$ 这层倒着循环的意义。比如在 $i$ 固定的情况下，$5$ 这个容量选择了第 $i$ 个物品，而 $7$ 这个容量又选择了 $i$ 和 $5$。可以发现 $i$ 这个物品已经选了两次了，不符合 $01$ 背包的定义。

现在可以重复选择了，$j$ 这一层正着循环就可以了。

优化3

两个物品 $i$ 和 $j$，如果 $w[i]>w[j]$ 且 $v[i]<v[j]$，就把 $i$ 去掉，不用考虑。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, v[200000], w[200000], f[2000000];
int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= n; i++)
        for(int j = w[i]; j <= m; j++)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    printf("%d", f[m]);
    return 0;
}

多重背包问题

Description

与 $01$ 背包相同，但每个物品可以取 $z$ 次。

Solution

做法1

把每个物品拆成 $z$ 个同样的物品，每个物品可以取一次。但是一旦 $z$ 比较大，这种做法在时空复杂度上就难以通过了。

优化1

把每个物品拆成一些捆，每一捆按照 $2$ 的次方数来拆。最后剩下的物品绑成一捆。

证明：
根据倍增的结论，某个数 $i$ 如果可以表示成 $2^0+2^1+2^2+ … +2^N$（设其为性质 $A$），那么任意一个数 $x$ $(1≤x≤i)$，也可以表示成 $2^a+2^b+2^c+ … +2^M$ $(0≤a<b<c< … <M≤N)$
在此题中，如果物品数量 $z$ 满足性质 $A$，小于等于 $z$ 的任何一个物品都可以表示出来。
否则，设 $p$ 为最大的 $<z$ 而满足性质 $A$ 的数。设要取 $i$ 件物品，分类讨论：
$1.$ $i≤p$，按照上述方法取。
$2.$ $p<i≤z$，先取最后一捆，再按照上述方法取。
QED.

Code

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
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int n, m, cnt = 0, ans = 0, v[100000], w[100000], f[9001];
signed main()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        int a, b, c, x = 1;
        scanf("%lld%lld%lld", &a, &b, &c);
        while(x <= c)
        {
            cnt++;
            v[cnt] = a * x, w[cnt] = b * x;
            c -= x, x *= 2;
        }
        if(c)
        {
            cnt++;
            v[cnt] = a * c;
            w[cnt] = b * c;
        }
    }
    n = cnt;
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    for(int i = 1; i <= m; i++) ans = max(ans, f[i]);
    printf("%lld", ans);
    return 0;
}

混合三种背包问题

Description

有一些物品只能取 $1$ 件，有一些物品可以取无数件，其他物品可以取 $z_i$ 件。

Solution

首先考虑 $01$ 背包和完全背包的混合。只要判断一下当前物品的种类，看看是要顺序还是逆序循环。加上多重背包：按照上面的方法，拆开物品，将其变成 $01$ 背包（听说可以使用单调队列）。

Code

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i++)
{
    if(can[i] == INF)
        for(int j = m; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + val[i]);
    else
        for(int j = w[i]; j <= m; j++)
            f[j] = max(f[j], f[j - w[i]] + val[i]);
}

二维费用背包问题

Description

对于每件物品，这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。

Solution

设 $f[i][u][v]$ 为前 $i$ 个物品，两种代价分别为 $u$ 和 $v$ 能够得到的最大价值。转移方程：
$f[i][u][v]=max(f[i-1][u-a[i]][v-b[i]]+val[i],f[i-1][u][v])$

可以按照上面优化，去掉 $i$ 这一维。只要注意 $01$ 背包是逆序循环，完全背包是顺序循环就行了。代码以 $01$ 背包为例。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 506;
int n, m1, m2, a[N], b[N], val[N], f[N][N];

int main()
{
    scanf("%d%d%d", &n, &m1, &m2);
    for(int i = 1; i <= n; i++)
        scanf("%d%d%d", &a[i], &b[i], &val[i]);
    for(int i = 1; i <= n; i++)
        for(int j = m1; j >= a[i]; j--)
            for(int k = m2; k >= a[i]; k--)
                f[j][k] = max(f[j][k], f[j - a[i]][k - b[i]] + val[i]);
    printf("%d", f[m1][m2]);
    return 0;
}

分组背包问题

Description

把 $n$ 个物品分为 $k$ 组，每一组物品最多只能选一个。

Solution

问题变成了，你可以选择本组的一件，或者一件也不选。设 $f[i][j]$ 为前 $k$ 组物品花费 $j$ 能得到的价值。转移方程：
$f[k][j]=max(f[k-1][j],f[k-1][j-w[i]]+val[i])$ （$i$ 属于第 $k$ 组）

可以按照上面的优化方法，把 $f$ 数组变成一维。保证每组只能选一个物品，容量的循环要在每一组物品的循环之外。具体看代码。

Code

1
2
3
4
5
6
7
for(int i = 1; i <= k; i++)
    for(int j = m; j > 0; j--)
        for(int h = 1; h <= cnt[i]; h++)
        {
            int v = belong[i][h];
            f[j] = max(f[j], f[j - w[v]] + val[v]);
        }

有依赖的背包问题

Description

如果选物品 $i$，必须选物品 $j$。

Solution

如果把问题转化为一棵树，若 $j$ 依赖于 $i$，使 $i$ 成为 $j$ 的父亲。连出一虚拟根。只有选择了 $i$，才能选择其子树。

设 $f[i][j]$ 为以 $i$ 为根的子树，已经选择了 $j$ 个节点的最大价值。转移方程：
$f[i][j]=max(f[i][j],f[s][k]+f[i][j-k])$ $(s$ 是 $i$ 的儿子，$0<k<j)$

例题

洛谷 P2014 选课

此题相当于给出 $n$ 个物品，背包容量为 $m$，每个物品的重量为 $1$，价值为 $s_i$，最大化价值。物品之间存在依赖关系。这样就把问题转化成了一般形式，按上面的思路解即可。

Code

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
42
43
44
#include <cstdio>
#include <iostream>
using namespace std;

const int N = 2333;
struct edge
{
    int nxt, to;
} e[N];
int n, m, fat, cnt = 0, s[N], f[N][N], head[N];

void add(int x, int y)
{
    e[++cnt] = (edge) { head[x], y };
    head[x] = cnt;
}

void dp(int x, int fa)
{
    f[x][1] = s[x];
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa) continue;
        dp(v, x);
        for(int j = m + 1; j > 0; j--)
            for(int k = 1; k < j; k++)
                f[x][j] = max(f[x][j], f[v][k] + f[x][j - k]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &fat, &s[i]);
        add(fat, i);
        add(i, fat);
    }
    dp(0, -1);
    printf("%d", f[0][m + 1]);
    return 0;
}

泛化背包问题

Description

每个物品没有固定的重量和价值。给它重量 $i$，就会得到价值 $h(i)$。

Solution

设有泛化物品 $h$ 和 $l$，其中 $i(j)$ 表示给 $i$ 这个泛化物品设置 $j$ 费用能得到的价值。若 $f$ 满足 $f(v)=max(h(k)+l(v-k))$，则称 $f=h+l$。

实际上求最终结果的过程，就是不断求泛化物品之和的过程。