二维费用背包

1 问题引入

普通背包只有一种「费用」——容量。但有些限制是两种同时存在的：

定义二维费用背包

有 $n$ 件物品和一个背包。第 $i$ 件物品需要付出两种费用 $a_i$ 和 $b_i$ ，可获得价值 $v_i$ 。两种费用各自有上限 $A$ 和 $B$ 。选哪些物品能使价值最大？

样例（两种费用分别叫「重量」和「体积」）：

2 加一维就行

费用多了一种，状态就多一维。设 $f(i,j,k)$ 表示前 $i$ 件物品、两种费用分别花掉 $j$ 、 $k$ 时的最大价值：

f(i,j,k)=\max\Bigl\{\,f(i-1,j,k),\; f(i-1,\,j-a_i,\,k-b_i)+v_i\,\Bigr\}

和 01 背包的式子一模一样，只是每处多了一个下标。

压掉 $i$ 这一维，用二维数组滚动：

// 二维费用背包：每件物品消耗两种费用 a、b，两个上限分别 A、B
// f[i][j] = 两种费用分别花 i、j 时的最大价值；两维都倒序，保证每件只用一次
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

int n, A, B;
int f[maxn][maxn];

int main() {
    cin >> n >> A >> B;
    for (int i = 1; i <= n; ++i) {
        int a, b, v;
        cin >> a >> b >> v;
        for (int j = A; j >= a; --j) {          // 第一维倒序
            for (int k = B; k >= b; --k) {      // 第二维倒序
                f[j][k] = max(f[j][k], f[j - a][k - b] + v);
            }
        }
    }
    cout << f[A][B] << endl;
    return 0;
}

输出：

说明两个维度都要倒序

一维背包倒序是为了「 $f[j-a_i]$ 还是上一轮的值」。二维同理： $f[j][k]$ 依赖 $f[j-a_i][k-b_i]$ ，所以 $j$ 和 $k$ 都必须倒序。少倒一个维度，物品就会被重复使用。

如果物品是完全背包类型（可用无限次），把两个维度都改成正序；如果是多重背包，按多重背包的方式拆分。

3 「件数」也是费用

有一类题目不明说「二维费用」，而是限制最多选几件：

有 $n$ 件物品和一个容量为 $C$ 的背包，最多只能选 $K$ 件，求最大价值。

这等价于给每件物品加了一种费用——「件数」，每件的件数费用恒为 $1$ ，总上限是 $K$ 。

于是状态自然写成 $f(cnt, j)$ ：选了 $cnt$ 件、容量花掉 $j$ 时的最大价值。两个维度都倒序：

// 「件数」当成第二种费用：最多选 K 件，容量 C
// f[cnt][j] = 选 cnt 件、容量 j 时的最大价值，两维都倒序
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;

int n, C, K;
int f[maxn][maxn];

int main() {
    cin >> n >> C >> K;
    for (int i = 1; i <= n; ++i) {
        int w, v;
        cin >> w >> v;
        for (int cnt = K; cnt >= 1; --cnt) {    // 件数倒序
            for (int j = C; j >= w; --j) {      // 容量倒序
                f[cnt][j] = max(f[cnt][j], f[cnt - 1][j - w] + v);
            }
        }
    }
    cout << f[K][C] << endl;
    return 0;
}

样例输入：

输出：

4 复整数视角

《背包问题九讲》里有一个挺有意思的类比：把「费用」看成数，一维背包的费用是自然数，二维背包的费用是复整数 $a+b\mathrm{i}$ 。

也就是说，二维费用背包并没有引入新东西，只是把一维问题里的「数」换成了「二维向量」，而所有运算（加法、比较）都逐分量进行。

说明这个视角有什么用

它提示了一个通用的改造方法：当题目多出一种约束时，先问「能不能把它写成一个新的费用维度」。能写成费用维度的，状态加一维就能解；写不成的（比如依赖关系、互斥关系），才需要换模型（分组背包、树形 DP）。

5 小结

二维费用背包的结论很短：加一维，两个维度都倒序。

但「件数也是费用」这个观察值得记住——很多看起来是新题目的限制，其实只是换了个名字的费用。

6 相关题解

暂无相关题解