题意

$N$ 种物品，背包容量 $V$、承重 $M$。每种物品有体积 $v_i$、重量 $w_i$、价值 $p_i$，每种只有一件。求在总体积 $\le V$ 且总重量 $\le M$ 下的最大总价值。

思路

一句话本质：多了一维容量，DP 状态从 dp[j] 变成 dp[j][k]，转移仍然是倒序枚举两维，每个物品只选一次。

先看暴力：

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
35import sys


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    V = next(it)
    M = next(it)
    items = []
    for _ in range(N):
        v = next(it)
        w = next(it)
        p = next(it)
        items.append((v, w, p))

    ans = 0

    def dfs(idx: int, vol: int, weight: int, val: int) -> None:
        nonlocal ans
        if vol > V or weight > M:
            return
        if idx == N:
            ans = max(ans, val)
            return
        v, w, p = items[idx]
        dfs(idx + 1, vol, weight, val)
        dfs(idx + 1, vol + v, weight + w, val + p)

    dfs(0, 0, 0, 0)
    print(ans)


if __name__ == '__main__':
    solve()

暴力 DFS 每个物品选/不选，时间复杂度 $O(2^N)$。$N=100$ 时 $2^{100}$ 完全不可行。

比普通 01 背包多了一维约束，DP 状态怎么扩展？

普通 01 背包的状态定义是 $dp[j]$：容量 $j$ 时的最大价值。现在多了一个"重量"约束，很自然地想到把状态扩展为 $dp[j][k]$：容量 $j$、承重 $k$ 时的最大价值。转移时两维都从大到小倒序枚举，保证每个物品只选一次。

转移方程怎么写？

选择物品 $i$ 时（体积 $v$、重量 $w$、价值 $p$），在剩余容量 $j \ge v$ 且剩余承重 $k \ge w$ 的前提下：

两维枚举顺序无所谓（先 $j$ 后 $k$ 或先 $k$ 后 $j$），但必须都是倒序——这和 01 背包倒序的道理完全一样：用到的 dp[j-v][k-w] 必须是处理当前物品之前的旧状态。

为什么这题只涉及 01 类型？

题面明确每种物品只有一件，所以是"二维费用的 01 背包"。如果某维约束对应的物品数量不同（如完全背包），只需把对应维改成正序即可，道理和混合背包中的 01/完全切换一样。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
// dp[j][k] 表示费用1容量为 j、费用2容量为 k 时的最大价值。
int dp[maxn][maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V, M;
    cin >> N >> V >> M;
    for (int i = 0; i < N; i++) {
        int v, w, p;
        cin >> v >> w >> p;                 // 费用1、费用2、价值
        // 二维费用 0/1 背包：两维都倒序，保证每件物品只选一次。
        for (int j = V; j >= v; j--)
            for (int k = M; k >= w; k--)
                dp[j][k] = max(dp[j][k], dp[j - v][k - w] + p);
    }
    cout << dp[V][M] << '\n';
    return 0;
}

复杂度

时间 $O(N \times V \times M)$，每个物品需要两维各遍历一次。空间 $O(V \times M)$。当 $N, V, M \le 100$ 时，约 $10^6$ 次操作，轻松通过。

总结

二维费用背包就是把 01 背包的"一维约束 + 一维 DP"直接扩充为"两维约束 + 二维 DP"，转移逻辑不变，倒序保证每物品只选一次。理解了一维 01，二维只是加一层循环。