背包模板

01背包问题

题目

有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的费用是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即\(f[i][v]\)表示前\(i\)件物品恰放入一个容量为\(v\)的背包可以获得的最大价值。则其状态转移方程便是：

\[f[i][v]=\max\{f[i-1][v],f[i-1][v-c[i]]+w[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])
            f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
}

1
2
3

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]);

恰好完全装满

初始化时，除了\(f[0]=0\)，其他\(f[1...V]\)都为\(-\infty\)。

完全背包问题

题目

有\(N\)种物品和一个容量为\(V\)的背包，每种物品都有无限件可用。第i种物品的费用是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令\(f[i][v]\)表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

\[f[i][v]=\max\{f[i-1][v-k*c[i]]+k*w[i]\ |\ 0\le k*c[i]\le v\}\]

二维版本一维版本

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])
            f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    }
}

1
2
3

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

多重背包问题

题目

有 \(N\) 种物品和一个容量是 \(V\) 的背包。

第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

基本思路

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有\(n[i]+1\)种策略：取0件，取1件……取\(n[i]\)件。令\(f[i][v]\)表示前\(i\)种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：

\[f[i][v]=\max\{f[i-1][v-k*c[i]]+k*w[i]\ |\ 0\le k\le n[i]\}\]

复杂度是\(O(V*Σn[i])\)。

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++)
        for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

二进制优化

（1）我们知道转化成01背包的基本思路就是：判断每件物品我是取了你好呢还是不取你好。

（2）我们知道任意一个实数可以由二进制数来表示，也就是\(2^0\)~\(2^k\)其中一项或几项的和。

（3）这里多重背包问的就是每件物品取多少件可以获得最大价值。

int cnt = 0;
for (int i = 1; i <= n; i++) {
    int a, b, s;
    cin >> a >> b >> s;
    int k = 1;
    while (k <= s) {
        cnt++;
        v[cnt] = k * a;
        w[cnt] = k * b;
        s -= k;
        k <<= 1;
    }

    if (s) {
        cnt++;
        v[cnt] = a * s;
        w[cnt] = b * s;
    }
}

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]);

分组背包问题

题目

有 \(N\) 组物品和一个容量是 \(V\) 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 \(v_{ij}\)，价值是 \(w_{ij}\)，其中 \(i\) 是组号，\(j\) 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

基本思路

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设\(f[k][v]\)表示前\(k\)组物品花费费用\(v\)能取得的最大权值，则有：

\[f[k][v]=\max\{f[k-1][v],f[k-1][v-c[i]]+w[i]\ |\ 物品i属于第k组\}\]

二维版本一维版本

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) {
        f[i][j] = f[i - 1][j];
        for (int k = 0; k < s[i]; k++) {
            if (j >= v[i][k])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }
    }

for (int i = 1; i <= n; i++)
    for (int j = m; j >= 0; j--)
        for (int k = 0; k < s[i]; k++)
            if (j >= v[i][k])
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

混合背包问题

for (int i = 1; i <= n; i++) {
    if (s[i] == -1) {       // 01背包
        for (int j = m; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    } else if (s[i] == 0) { // 完全背包
        for (int j = v[i]; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    } else if (s[i] > 0) {  // 多重背包
        int cnt = 0, k = 1;
        while (k <= s[i]) {
            cnt ++;
            w1[cnt] = w[i] * k;
            v1[cnt] = v[i] * k;
            s[i] -= k;
            k <<= 1;
        }

        if (s[i]) {
            cnt ++;
            w1[cnt] = w[i] * s[i];
            v1[cnt] = v[i] * s[i];
        }

        for (int j = 1; j <= cnt; j++)
            for (int k = m; k >= v1[j]; k--)
                dp[k] = max(dp[k], dp[k - v1[j]] + w1[j]);
    }
}

二维费用的背包问题

问题

对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第\(i\)件物品所需的两种代价分别为\(a[i]\)和\(b[i]\)。两种代价可付出的最大值（两种背包容量）分别为\(V\)和\(U\)。物品的价值为\(w[i]\)。

基本思路

费用加了一维，只需状态也加一维即可。设\(f[i][v][u]\)表示前\(i\)件物品付出两种代价分别为\(v\)和\(u\)时可获得的最大价值。状态转移方程就是：

\[f[i][v][u]=\max\{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]\}\]

三维版本二维版本

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= V; j++)
        for (int k = 0; k <= U; k++) {
            dp[i][j][k] = dp[i - 1][j][k];
            if (j >= v[i] && k >= m[i])
                dp[i][j][k] = max(dp[i][j][k], 
                                  dp[i - 1][j - v[i]][k - m[i]] + w[i]);
        }

for (int i = 1; i <= n; i++)
    for (int j = V; j >= v[i]; j--)
        for (int k = U; k >= m[i]; k--)
            dp[j][k] = max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);

输出方案

一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。

还是以01背包为例，方程为\(f[i][v]=\max\{f[i-1][v],f[i-1][v-c[i]]+w[i]\}\)。再用一个数组\(g[i][v]\)，设\(g[i][v]=0\)表示推出\(f[i][v]\)的值时是采用了方程的前一项（也即\(f[i][v]=f[i-1][v]\)），\(g[i][v]\)表示采用了方程的后一项。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品。那么输出方案的伪代码可以这样写（设最终状态为\(f[N][V]\)）：

i=N
v=V
while(i>0)
    if(g[i][v]==0)
        print "未选第i项物品"
    else if(g[i][v]==1)
        print "选了第i项物品"
        v=v-c[i]

另外，采用方程的前一项或后一项也可以在输出方案的过程中根据\(f[i][v]\)的值实时地求出来，也即不须纪录\(g\)数组，将上述代码中的\(g[i][v]==0\)改成\(f[i][v]==f[i-1][v]\)，\(g[i][v]==1\)改成\(f[i][v]==f[i-1][v-c[i]]+w[i]\)也可。

输出字典序最小的最优方案

一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略。首先，子问题的定义要略改一些。我们注意到，如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为\(V-c[1]\)，物品为\(2..N\)的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为\(V\)，物品为\(2..N\)的子问题。不管答案怎样，子问题的物品都是以\(i..N\)而非前所述的\(1..i\)的形式来定义的，所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。

在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从\(N\)到\(1\)输入时，如果\(f[i][v]==f[i-v]\)及\(f[i][v]==f[i-1][f-c[i]]+w[i]\)同时成立，应该按照后者（即选择了物品\(i\)）来输出方案。

如果\(f(1,m)=f(2,m−v[1])+w[1]\)，说明选取了第\(1\)个物品可以得到最优解。
如果\(f(1,m)=f(2,m)\)，说明不选取第一个物品才能得到最优解。

如果\(f(1,m)=f(2,m)=f(2,m−v[1])+w[1]\)，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。

for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

for (int i = n; i; i--)
    for (int j = 0; j <= m; j++) {
        dp[i][j] = dp[i + 1][j];
        if (j >= v[i])
            dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
    }

int i = 1, j = m;
while (i <= n) {
    if (j >= v[i] && dp[i + 1][j - v[i]] + w[i] >= dp[i + 1][j]) {
        cout << i << ' ';
        j -= v[i];
    }
    i++;
}

求方案总数

对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。

对于这类改变问法的问题，一般只需将状态转移方程中的\(max\)改成\(sum\)即可。例如若每件物品均是完全背包中的物品，转移方程即为

\[f[i][v]=\sum\{f[i-1][v],f[i][v-c[i]]\}\]

初始条件\(f[0][0]=1\)。

求最优方案数

这里的最优方案是指物品总价值最大的方案。以01背包为例。

结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：\(dp[i][v]\)意义同前述，\(g[i][v]\)表示这个子问题的最优方案的总数。

memset(dp, -0x3f, sizeof dp);
dp[0] = 0, g[0] = 1;

for (int i = 0; i < n; i++) {
    int v, w;
    cin >> v >> w;
    for (int j = m; j >= v; j--) {
        int maxw = max(dp[j], dp[j - v] + w);

        int cnt = 0;
        if (dp[j] == maxw)
            cnt += g[j];
        if (dp[j - v] + w == maxw)
            cnt += g[j - v];
        dp[j] = maxw;
        g[j] = cnt % mod;
    }
}

int res = 0;
for (int i = 0; i <= m; i++)
    res = max(res, dp[i]);

int ans = 0;
for (int i = 0; i <= m; i++) {
    if (res == dp[i])
        ans = (ans + g[i]) % mod;
}

cout << ans << endl;

求最大值最小值初始化总结

二维情况

体积至多\(j\)，\(f[i,k] = 0\)，\(0 \le i \le n\), \(0 \le k \le m\)（只会求价值的最大值）
体积恰好\(j\)，
- 当求价值的最小值：\(f[0][0] = 0\), 其余是\(\infty\)
- 当求价值的最大值：\(f[0][0] = 0\), 其余是\(-\infty\)
体积至少\(j\)，\(f[0][0] = 0\)，其余是\(\infty\)（只会求价值的最小值）

一维情况

体积至多\(j\)，\(f[i] = 0\), \(0 \le i \le m\)（只会求价值的最大值）
体积恰好\(j\)，
- 当求价值的最小值：\(f[0] = 0\), 其余是\(\infty\)
- 当求价值的最大值：\(f[0] = 0\), 其余是\(-\infty\)
体积至少\(j\)，\(f[0] = 0\)，其余是\(\infty\)（只会求价值的最小值）