疯狂的背包问题(15) - 泛化物品背包问题

题意

$N$ 个泛化物品，背包容量 $V$ 。每个物品不是一个固定价值，而是一个函数 $f_i(x)$ ：花 $x$ 容量得 $f_i(x)$ 价值（由若干关键点分段线性插值，价值向下取整）。每个物品只能分配一次容量，求最大总价值。

思路

一句话本质：每个物品对应一个分段线性函数 $f(x)$ 。先用关键点插值得到 $val[c] = f(c)$ （ $0 \le c \le V$ ），然后倒序 DP： $dp[j] = \max(dp[j], dp[j - x] + val[x])$ ，枚举分配给当前物品的容量 $x$ 。

先看暴力：

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
45
46
47
48import sys


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    V = next(it)
    f = []
    for _ in range(N):
        K = next(it)
        points = []
        for __ in range(K):
            x = next(it)
            y = next(it)
            points.append((x, y))
        vals = [0] * (V + 1)
        for x in range(V + 1):
            if x <= points[0][0]:
                vals[x] = points[0][1]
            elif x >= points[-1][0]:
                vals[x] = points[-1][1]
            else:
                for j in range(len(points) - 1):
                    x1, y1 = points[j]
                    x2, y2 = points[j + 1]
                    if x1 <= x <= x2:
                        t = (x - x1) / (x2 - x1)
                        vals[x] = int(y1 + t * (y2 - y1))
                        break
        f.append(vals)

    ans = 0

    def dfs(idx: int, remaining: int, cur_val: int) -> None:
        nonlocal ans
        if idx == N:
            ans = max(ans, cur_val)
            return
        for x in range(remaining + 1):
            dfs(idx + 1, remaining - x, cur_val + f[idx][x])

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


if __name__ == '__main__':
    solve()

暴力对每个物品枚举分配 0 到 $V$ 的所有容量，DFS 搜索。当 $N=100$ 、 $V=100$ 时，分支因子约 101，指数级不可行。

泛化物品和普通 01 背包有什么区别？

普通 01 背包中，一个物品是固定的 $(v, w)$ ：花 $v$ 容量，得 $w$ 价值。泛化物品则是一整条函数曲线：花不同的容量，得到不同的价值。你可以给某个物品分配 0 容量（不选）、1 容量、2 容量……每种分配量对应不同的收益。

怎么把这个函数变成 DP 能用的数据？

第一步是"离散化"——把函数变成一张表 $val[c] = f(c)$ ，其中 $c = 0, 1, \dots, V$ 。对于关键点之间的容量 $x$ ，用相邻关键点的线性插值计算 $f(x)$ ，并向下取整。

有了 val[c] 后怎么做 DP？

对于每个泛化物品 $i$ ，我们有一个数组 $val_i[0 \dots V]$ 。要把它"装入"背包——本质上是一个容量分配决策：给物品 $i$ 分配 $x$ 容量（ $0 \le x \le V$ ），获得 $val_i[x]$ 价值。转移方程：

dp[j] = \max_{0 \le x \le j}(dp[j],\ dp[j - x] + val_i[x])

$j$ 从 $V$ 到 $0$ 倒序枚举，因为每个物品只能分配一份容量（不能把同一份容量反复分给同一个物品，否则相当于拿了多次）。分配量 $x$ 从 $0$ 到 $j$ 遍历。

这本质上是 01 背包的一种推广吗？

是的。普通 01 背包是泛化物品的特例：函数曲线只有两个点——分配 $v$ 容量得 $w$ 价值，分配其他容量得 0。泛化物品把这条曲线延展成了"花多少容量得多少价值"的任意函数，DP 转移则从"选/不选一个固定点"变成了"在所有可能的分配量中选一个最优的"。

代码

cpp

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 <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V;
    cin >> N >> V;
    // dp[j] 表示容量为 j 时的最大价值。
    vector<int> dp(V + 1, 0);
    for (int i = 0; i < N; i++) {
        int K;
        cin >> K;                        // 函数的关键点数量
        vector<pair<int, int>> points(K);
        for (int j = 0; j < K; j++)
            cin >> points[j].first >> points[j].second;

        // val[x] 表示该泛化物品消耗容量 x 时获得的价值（分段线性）。
        vector<int> val(V + 1, 0);
        for (int x = 0; x <= V; x++) {
            if (x <= points[0].first) {
                val[x] = points[0].second;
            } else if (x >= points.back().first) {
                val[x] = points.back().second;
            } else {
                for (int j = 0; j < K - 1; j++) {
                    int x1 = points[j].first, y1 = points[j].second;
                    int x2 = points[j + 1].first, y2 = points[j + 1].second;
                    if (x1 <= x && x <= x2) {
                        double t = (double)(x - x1) / (x2 - x1);
                        val[x] = (int)(y1 + t * (y2 - y1));
                        break;
                    }
                }
            }
        }

        // 0/1 背包倒序枚举容量，尝试分配给当前物品不同容量 x。
        for (int j = V; j >= 0; j--)
            for (int x = 0; x <= j; x++)
                dp[j] = max(dp[j], dp[j - x] + val[x]);
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

预处理每个物品的 $val$ 表： $O(N \times V \times K)$ ，其中 $K$ 是关键点数量（ $\le 10$ ），需要为每个容量找所在插值段。DP 转移： $O(N \times V^2)$ ，每个物品需枚举容量 $j$ 和分配量 $x$ 两层循环。总复杂度 $O(NV^2)$ ， $N, V \le 100$ 时约 $10^6$ ，可以通过。

空间 $O(V)$ 。

总结

泛化物品把"物品 = 固定 (体积, 价值)“推广为"物品 = 函数 (容量 → 价值)”，DP 思路也相应地从"选/不选"推广为"分配多少容量"。核心是两步：插值预计算 $val[c] = f(c)$ ，然后像 01 背包一样倒序 DP 枚举分配量。

疯狂的背包问题(15) - 泛化物品背包问题

目录

题意

思路

代码

复杂度

总结