背包问题

01 背包

样例：

4 10
2 1
3 3
4 5
7 9

12

// 深搜方式
#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int vi[N], wi[N], n, v, ans;

// u 代表当前考虑的物品，物品编号从0开始
// vv 代表已选物品的体积之和
// ww 代表已选物品体积之和是vv时的最大价值
void dfs(int u, int vv, int ww) {
    if (u >= n) {
        if (ww > ans) ans = ww;
        return;
    }

    dfs(u + 1, vv, ww); // 不选第 u 件物品
    if (vv + vi[u] <= v) { // 如果 当前的总体积加上第 u 件物品的体积小于规定体积
        dfs(u + 1, vv + vi[u], ww + wi[u]); // 选第 u 件物品
    }
}

int main() {
    cin >> n >> v;
    for (int i = 0; i < n; i++) {
        cin >> vi[i] >> wi[i];
    }

    dfs(0, 0, 0);
    cout << ans << endl;

    return 0;
}

动态规划：

1. 阶段划分：按已处理物品的件数将选择过程划分为 $n$ 个阶段，设阶段变量 $i$ 代表前 $i$ 件物品
2. 设计状态：
   1. 设 $f[i][j]$ 表示将前 $i$ 件物品选择若干件放入体积为 $j$ 的背包获得的最大价值（体积 $j$ 可以不装满）。
   2. 设 $f[i][j]$ 表示将前 $i$ 件物品选择若干件恰好放入体积为 $j$ 的背包获得的最大价值（体积 $j$ 必须装满）。
3. 决策：考虑第 $i$ 件物品选还是不选。
4. 状态转移方程：$$f(i,j)=max\{\begin{array}{ll}f(i-1,j),& \mathrm{不}\mathrm{选}\mathrm{第}i\mathrm{件}\mathrm{物}\mathrm{品}\\ f(i-1,j-v[i])+w[i],& j\ge v[i],\mathrm{选}\mathrm{第}i\mathrm{件}\mathrm{物}\mathrm{品}\end{array}$$
5. 边界：
   1. 对应第一种状态表示：$f[i][j]=0$。
   2. 对应第二种状态表示：$f[0][0]=0$，其余的 $f[i][j]=-\mathrm{\infty }$
6. 目标解：
   1. 对应第一种状态表示：$f[n][m]$
   2. 对应第二种状态表示：$max(f[n][j])(0\le j\le m)$

下面的参考代码使用的是第一种状态表示方式！

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N][N], v[N], w[N], n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[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]);
            }
        }
    }

    cout << f[n][m] << endl;

    return 0;
}

习题：洛谷 P1048：采药

参见 01 背包的思考方式！

01 背包的优化

4 10
2 1
3 3
4 5
7 9

12

垂直箭头代表不选第 4 种物品，而斜线箭头代表选择第 4 件物品。

滚动数组优化：

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[2][N], v[N], w[N], n, m;

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

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i & 1][j] = f[(i - 1) & 1][j]; // 左边集合
            if (j >= v[i]) {
                f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - v[i]] + w[i]);
            }
        }
    }

    cout << f[n & 1][m] << endl;

    return 0;
}

降维优化：$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);$

$f[i][j]$ 的计算只与第 $i-1$ 层有关，因此可以使用滚动数组的思想进行优化，因为 $j>=v[i]$，如果让 $j$ 从小到大循环 $j-v[i]<j$，计算第 $i$ 层的结果时使用的就是已经修改过的 $j-v[i]$，所以 $j$ 从大到小循环。

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N], v[N], w[N], n, m;

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

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

    cout << f[m] << endl;

    return 0;
}

阅读提升：对于 01 背包问题一种使用集合的思考方式：

状态表示：$f[i][j]$

集合：只从前 $i$ 个物品中选，总体积是 $j$ 的选法集合
属性：只从前 $i$ 个物品中选，总体积是 $j$ 的价值最大值

选法集合有哪些呢？

a. 选第 $i$ 件物品 -> $f[i - 1][j]$
b. 不选第 $i$ 件物品 -> $f[i - 1][j - v[i]] + w[i]$

状态计算：$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);$

完全背包

1. 阶段划分：按已处理物品的件数将选择过程划分为 $n$ 个阶段，设阶段变量 $i$ 代表前 $i$ 件物品
2. 设计状态：设 $f[i][j]$ 表示将前 $i$ 件物品选择若干件放入体积为 $j$ 的背包获得的最大价值（体积 $j$ 可以不装满）。
3. 决策：考虑第 $i$ 件物品选 $k(0\le k\le \frac{j}{v[i]})$ 件。
4. 状态转移方程：$f[i][j]=max(f[i-1][j-k\ast v[i]]+k\ast w[i])(0\le k\le \frac{j}{v[i]})$
5. 边界：$f[i][j]=0$
6. 目标解：$f[n][m]$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N][N], v[N], w[N], n, m;

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

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

    cout << f[n][m] << endl;

    return 0;
}

习题：洛谷 P1616 疯狂的采药

参见完全背包的思考方式！

完全背包的优化

考虑进一步优化状态转移方程：

$v$ 代表第 $i$ 件物品的体积 $w$ 代表第 $i$ 件物品的价值

1. f[i][j] = max(f[i - 1, j], f[i - 1, j - v] + w, f[i - 1, j - 2v] + 2w, f[i - 1, j - 3v] + 3w, ....)
2. f[i][j - v] = max(f[i - 1, j - v], f[i - 1, j - 2v] + w, f[i - 1, j - 3v] + 2w, ....) 所以有：$f[i][j]=max(f[i-1][j],f[i][j-v]+w)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N][N], v[N], w[N], n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[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][j - v[i]] + w[i]);
        }
    }

    cout << f[n][m] << endl;

    return 0;
}

继续优化：类比 01 背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N], v[N], w[N], n, m;

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

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

    cout << f[m] << endl;

    return 0;
}

阅读提升：对于完全背包问题一种使用集合的思考方式：

状态表示：$f[i][j]$

集合：只从前 $i$ 种物品中选，总体积是 $j$ 的选法集合
属性：只从前 $i$ 种物品中选，总体积是 $j$ 的价值最大值

选法集合有哪些呢？第 $i$ 件物品可以选 $0、1、2...k$ 件，$k$ 不是无限大的，有体积 $j$ 的限制

状态计算：$f[i][j]=max(f[i-1][j-k\ast v[i]]+k\ast w[i]);$

多重背包 I & II

以完全背包的思路来做多重背包，只需要考虑每种物品的数量即可。时间复杂度：$O(N\ast V\ast S)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N][N], v[N], w[N], s[N], n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> s[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k * v[i] <= j && k <= s[i]; k++) { // 考虑数量
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
            }
        }
    }

    cout << f[n][m] << endl;

    return 0;
}

二进制优化：将多重背包看成01 背包问题。时间复杂度：$O(N\ast V\ast \log S)$

#include <bits/stdc++.h>

using namespace std;

const int N = 25000;
int f[N], w[N], v[N];

int main() {
    int n, m; cin >> n >> m;

    int idx = 0;
    for (int i = 0; i < n; i++) {
        int a, b, s;
        cin >> a >> b >> s;

        int k = 1;
        while (k <= s) {
            idx++;
            v[idx] = a * k;
            w[idx] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0) {
            idx++;
            v[idx] = a * s;
            w[idx] = b * s;
        }
    }

    n = idx;
    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]);
        }
    }

    cout << f[m] << endl;

    return 0;
}

分组背包

1. 阶段划分：按已处理的组数将问题求解过程划分为 $n$ 个阶段，设阶段变量 $i$ 代表前 $i$ 组
2. 设计状态：设 $f[i][j]$ 表示从前 $i$ 组物品种选择若干件放入体积为 $j$ 的背包的最大价值和
3. 决策：考虑第 $i$ 组物品选 $0$ 件还是选 $1$ 件，若选 $1$ 件则需枚举第 $i$ 组所有物品考虑选哪一件？
4. 状态转移方程：$$f(i,j)=max\{\begin{array}{ll}f(i-1,j),& \mathrm{第}i\mathrm{组}\mathrm{物}\mathrm{品}\mathrm{选}0\mathrm{件}\\ f(i-1,j-v[i][k])+w[i][k],& j\ge v[i][k],\mathrm{第}i\mathrm{组}\mathrm{物}\mathrm{品}\mathrm{选}\mathrm{第}k\mathrm{件}\end{array}$$
5. 边界与目标解：
   1. 边界：$f[i][j]=0$
   2. 目标解：$f[n][m]$

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int w[N][N], v[N][N], s[N];
int f[N][N];

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }

    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; k <= s[i]; k++) { // 第 i 组物品选第 k 个，只选一个
                if (v[i][k] <= j) {
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
                }
            }
        }
    }

    cout << f[n][m] << endl;

    return 0;
}

分组背包的优化

类比 01 背包的优化方式

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int w[N][N], v[N][N], s[N];
int f[N];

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 0; j--) { // 体积从大到小循环
            for (int k = 1; k <= s[i]; k++) {
                if (v[i][k] <= j) {
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

洛谷 P1757：通天之分组背包

方案数问题

AcWing 278. 数字组合

给定  $N$  个正整数  $A_1,A_2,\dots ,A_N$，从中选出若干个数，使它们的和为  $M$，求有多少种选择方案。

分析：$n$ 件物品放进体积为 $m$ 的背包，求方案数（01 背包问题）。设 $f(i,j)$ 表示前 $i$ 数中选择若干数且和为 $j$ 时的方案数。对于第 $i$ 个数决策有选或不选，这两种方案之和即是 $f(i,j)$。

$f(i,j)=f(i-1,j)+f(i-1,j-a[i]),(j\ge a[i])$

边界条件：$f(i,0)=1$，前 $i$ 个数中取若干数和为 $0$ 只用一种方案（全不取）。其余为 $0$

目标解：$f(n,m)$

for (int i = 0; i <= n; i++) f[i][0] = 1;

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        f[i][j] = f[i - 1][j];
        if (j >= a[i]) {
            f[i][j] += f[i - 1][j - a[i]];
        }
    }
}

cout << f[n][m] << endl;

请你完成降维优化的工作！

AcWing 279. 自然数拆分

给定一个自然数  $N$，要求把  $N$  拆分成若干个正整数相加的形式，参与加法运算的数可以重复。

注意:

• 拆分方案不考虑顺序；
• 至少拆分成  2  个数的和。

求拆分的方案数  mod 2147483648  的结果。

分析：给定 $n$ 个物品 $(1\sim n)$，放到体积为 $n$ 的背包中，每件物品可以重复选，求方案数（完全背包）。设 $f(i,j)$ 表示前 $i$ 数中选择若干数且和为 $j$ 时的方案数。对于第 $i$ 个数决策是选 $k(0\le k\le \frac{j}{i})$ 件，所有方案之和即是 $f(i,j)$。

$f(i,j)=sum(f(i-1,j-i\times k))$

边界条件：$f(i,0)=1$，前 $i$ 个数中取若干数和为 $0$ 只用一种方案（全不取）。其余为 $0$

目标解：$f(n,n)$

注意：

• 至少拆分成 $2$ 个数
• 2147483648 爆 int

for (int i = 0; i <= n; i++) f[i][0] = 1;

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 0; k * i <= j; k++) {
            f[i][j] += f[i - 1][j - i * k];
        }
    }
}

cout << (f[n][n] - 1) % 2147483648 << endl;

注：以上代码提交之后会爆空间，请你完成降维优化的工作！

习题

1. 洛谷 P2842：纸币问题 1
2. 洛谷 P2840：纸币问题 2
3. 洛谷 P2834：纸币问题 3

可行性问题

AcWing 280. 陪审团

分析：该题可以看作是具有多个体积维度的01 背包。把 $N$ 个候选人看作 $N$ 件物品，那么每件物品都有 3 个体积：

• 人数：每个候选人的人数都是 $1$，填满容积为 $M$ 的背包
• 辩方得分：即辩方给候选人打的分数 $d_i$，取值在 $1\sim 20$
• 控方得分：即控方给候选人打的分数 $p_i$，取值在 $1\sim 20$

设 $f(i,j,d,p)$ 表示考虑前 $i$ 个人，$j$ 个人入选，当前辩方总得分为 $d$，控方总得分为 $p$ 时的状态是否可行。

$f(i,j,d,p)=f(i-1,j,d,p)\vee f(j-1,d-d_i,p-p_i)$

边界：$f(0,0,0,0)=true$ 其余均为 $false$

目标：找到一个状态 $f(n,m,d,p)$，满足 $f(n,m,d,p)=1$，并且 $|d-p|$ 尽量小，如果 $|d-p|$ 相同，则 $d+p$ 尽量大。

可以将阶段这个维度优化掉。$f(j,d,p)$

以上我们可以求出满足条件的辩方总分和控方总分，如果需要输出具体方案，请参考

AcWing 281. 硬币

分析：该题属于多重背包模型，其中物品是硬币，体积为面值，$M$ 为背包总容积。题目求解的是“是否可以拼成面值 $S$”是一个可行性问题。

设 $f(i,j)$ 表示前 $i$ 种硬币能否拼成面值 $j$

$f(i,j)=f(i,j)\vee f(i-1,j-a_i\ast k)$

边界：$f(i,0)=true$

目标：$sum(f(n,1\sim m)=true)$

注意：直接提交朴素代码会超时（考虑二进制优化），请你完成降维优化工作。

二维费用背包

看电影

新学期到了，朵朵明天要去上学。她决定今晚要玩得开心。她非常喜欢看电影。所以她想让她叔叔买些电影，今晚和她一起看。但是爷爷只给他们 $L$ 分钟看电影。之后他们就必须得睡觉了。

朵朵列了 $N$ 部电影，编号从 $1$ 到 $N$，都是她最喜欢的，每部电影都有一个快乐值 $V_i(V_i>0)$。$V_i$ 越高，说明朵朵越喜欢它，朵朵的总快乐值就会累加上它。每部电影都有一个播放时间 $T_i$ 分钟。如果一部电影朵朵选择看，那么她就一定看完。

但是有一个奇怪的问题，店里只卖 $M$ 部电影(不少也不多) ，这让她的叔叔很难做决定。如何从 $N$ 张 DVD 中选择 $M$ 张，使朵朵最快乐且花费的时间不超过 $L$。

1      // Q 组测试数据
3 2 10 // N M L
11 100 // T1 V1
1 2    // T2 V2
9 1    // T3 V3

3      // 输出

分析：二维费用背包。本题中，每部电影的选择产生的费用有两个：一是花费了播放时间，二是占用了一部电影的名额。背包的体积也受到两个费用的限制：一是总的播放时间，二是总的电影数量。

设 $f(i,j,k)$ 表示从前 $i$ 部电影中选择 $j$ 部电影且播放时间恰好为 $k$ 的最大快乐值。考虑第 $i$ 部电影选还是不选。

状态转移方程：

$$f(i,j,k)=max\{\begin{array}{ll}f(i-1,j,k),& \mathrm{选}\mathrm{第}i\mathrm{部}\mathrm{电}\mathrm{影}\\ f(i-1,j-1,k-t_i)+v_i,& j\ge 1\mathrm{且}k\ge t_i,\mathrm{不}\mathrm{选}\mathrm{第}i\mathrm{部}\mathrm{电}\mathrm{影}\end{array}$$

边界：$f(0,0,0)=0$ 其余为负无穷

目标解：$max(f(n,m,k))$ $(0\le k\le l)$

该题可以看作是 01 背包变形，请你完成降维优化的工作！

拓展

多维费用背包

依赖背包

动态变化的背包问题