01背包

GitHub跳转原题关系图返回列表

体积只有 300 种,按体积分组取价值最大的前缀;固定余数把容量拆成独立链后,前缀和的凹性给出决策单调性,用分治优化把 O(nm) 降到 O(n log n + Σ m log(m/s))。

OJ: roj

题目 ID: 1786

难度:提高+/省选-

标签:动态规划背包01背包决策单调性分治前缀和python

创建: 2026-10-08 02:28

更新: 2026-10-08 02:28

形式化题目

有 nn 件物品,第 ii 件体积 sis_i、价值 viv_i,每件最多选一次。对每一个容量 j=1,2,…,mj = 1, 2, \dots, m 独立求解一次 0/1 背包,输出 mm 个最大价值。

数据规模:

1⩽n⩽106,1⩽m⩽105,1⩽si⩽300,1⩽vi⩽109.1 \leqslant n \leqslant 10^6,\quad 1 \leqslant m \leqslant 10^5,\quad 1 \leqslant s_i \leqslant 300,\quad 1 \leqslant v_i \leqslant 10^9.

记 dp[j]dp[j] 为容量不超过 jj 时能取得的最大价值(jj 单调不减的阶梯函数), 答案即 dp[1],dp[2],…,dp[m]dp[1], dp[2], \dots, dp[m]。

朴素做法对每个 jj 各跑一遍 0/1 背包,或写成 for j: for i: dp=..., 复杂度 O(nm)=1011O(nm) = 10^{11},必然超时。

正解

思路

第一步:按体积分组。

体积只有 300300 种,这是本题唯一的突破口。把物品按体积 ss 分成 300300 组。 同一组内物品体积完全相同,因此"在容量 jj 里取 kk 个体积 ss 的物品"这件事, 取得的最大收益一定是组内价值最大的那 kk 个之和 —— 与取哪几个无关,只与 kk 有关。

于是每组内把价值降序排序,做前缀和

pre[k]=组内价值最大的 k 个之和,pre[0]=0,pre[k] = \text{组内价值最大的 } k \text{ 个之和},\qquad pre[0] = 0,

(第 kk 个的贡献是组内第 kk 大价值,kk 超过组内物品数时贡献为 00, 相当于补上若干体积 ss、价值 00 的“幽灵物品”。因为 dpdp 单调不减, 取幽灵物品永远不会更优,所以“常数延拓”是无损的,而且能顺带消掉 “每个容量最多取 ∣Gs∣|G_s| 个”的窗口约束,实现更简洁。)

关键性质:因为价值已降序,增量 pre[k] - pre[k-1] = $ 组内第 $k 大价值单调不增, 所以 prepre 是凹函数(离散意义下增量单调不增)。

第二步:按组做一次“完全背包式”的整组转移。

设当前 dp[j]dp[j] 为已处理过的若干组、容量不超过 jj 的最大价值。加入体积 ss 这一组:

dp′[j]=max⁡0⩽k⩽⌊j/s⌋(dp[j−k s]+pre[k]).(1)dp'[j] = \max_{0 \leqslant k \leqslant \lfloor j/s \rfloor} \Big( dp[j - k\,s] + pre[k] \Big). \tag{1}

这就是一个“同一种物品可重复取、但第 kk 个的收益为 pre[k]−pre[k−1]pre[k]-pre[k-1]”的 无界完全背包(幽灵物品贡献为 00,不改变最优值,所以不必再设个数上界)。

第三步:固定余数,拆成独立链。

(1) 式里 jj 与 j−ksj - ks 模 ss 同余。对每个余数 r∈[0,s)r \in [0, s),令

j=r+i s (0⩽i⩽Lr),f[i]=dp[r+i s],g[i]=dp′[r+i s],j = r + i\,s \ (0 \leqslant i \leqslant L_r),\qquad f[i] = dp[r + i\,s],\qquad g[i] = dp'[r + i\,s],

则 (1) 变成 ss 条互不干扰的一维链(这是标准的“同类同余”卷积):

g[i]=max⁡0⩽t⩽i(f[t]+pre[i−t]).(2)g[i] = \max_{0 \leqslant t \leqslant i} \Big( f[t] + pre[i - t] \Big). \tag{2}

下标 tt 的语义是"从旧链位置 tt 转移而来",等价于在本组取了 i−ti - t 个物品。

第四步:决策单调性 + 分治优化。

(2) 式对固定 ii 求 argmax。设两个决策 t1<t2t_1 < t_2,若在 ii 处 t2t_2 比 t1t_1 优:

f[t2]+pre[i−t2]⩾f[t1]+pre[i−t1].f[t_2] + pre[i - t_2] \geqslant f[t_1] + pre[i - t_1].

ii 增大 11 时,左边增量是 pre[i+1−t2]−pre[i−t2]pre[i+1-t_2]-pre[i-t_2], 右边增量是 pre[i+1−t1]−pre[i−t1]pre[i+1-t_1]-pre[i-t_1];由 prepre 凹(增量单调不增)且 i+1−t2<i+1−t1i+1-t_2 < i+1-t_1,左增量 ⩾\geqslant 右增量,即优势不会反转。

所以 argmax opt(i)opt(i) 关于 ii 单调不减。这正是分治优化的适用条件:

text
solve(l, r, optl, optr):        # 求解 g[l..r],已知 opt(i) ∈ [optl, optr]
    mid = (l+r)/2
    在 [optl, min(optr, mid)] 内暴力找 opt(mid) 并填 g[mid]
    solve(l,   mid-1, optl,  opt(mid))
    solve(mid+1, r,    opt(mid), optr)

每条链长度 Lr≈m/sL_r \approx m/s,代价 O(Lrlog⁡Lr)O(L_r \log L_r)(每层均摊 O(Lr)O(L_r))。 对固定的 ss,所有链合起来 O(mlog⁡(m/s))O(m \log(m/s))。

总复杂度:

O(n+mlog⁡m+∑s=1300mlog⁡ms)≈3×108,O\Big(n + m \log m + \sum_{s=1}^{300} m \log \frac{m}{s}\Big) \approx 3 \times 10^8,

在 7000 ms 限时下 C++ 可以过(ss 越大链越短,∑slog⁡(m/s)\sum_s \log(m/s) 远小于 300log⁡m300 \log m)。

细节: 体积 s>ms > m 的物品任何容量都装不下,直接丢弃;答案用 dp[1..m]dp[1..m], dpdp 全程保持单调(初始全 00,(2) 式的转移保序性由 prepre 单调保证)。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 02:28
# update_at: 2026-10-08 02:28

import sys


def chain(f: list[int], pre: list[int]) -> list[int]:
    """回答"一条同余链上每个位置的最佳转移":返回转移后的链 g。

    链上第 i 个位置的容量是 r + i*s,g[i] = max{ f[t] + pre[i-t] : 0 <= t <= i }。
    pre 是凹函数(增量单调不增),故任意两个决策点 t1 < t2 的优劣至多反转一次,
    argmax 关于 i 单调不减 —— 用分治优化,每个结点只扫 [optl, mid] 这一段。
    显式栈代替递归,避免链长达 1e5 时爆栈。
    """
    length = len(f) - 1
    g = [0] * (length + 1)
    stack = [0, length, 0, length]    # 依次压入 (左界, 右界, 决策下界, 决策上界)
    while stack:
        opt_hi = stack.pop(); opt_lo = stack.pop()
        right = stack.pop(); left = stack.pop()
        mid = (left + right) >> 1
        lo = opt_lo
        hi = opt_hi if opt_hi < mid else mid   # 转移来源 t 不能超过当前位 i
        best = f[lo] + pre[mid - lo]
        best_t = lo
        for t in range(lo + 1, hi + 1):
            cand = f[t] + pre[mid - t]
            if cand > best:
                best = cand
                best_t = t
        g[mid] = best
        if left <= mid - 1:                   # 左半段的决策上界收到 best_t
            stack += (left, mid - 1, opt_lo, best_t)
        if mid + 1 <= right:                  # 右半段的决策下界抬到 best_t
            stack += (mid + 1, right, best_t, opt_hi)
    return g


def use_group(dp: list[int], values: list[int], s: int) -> None:
    """把体积为 s 的一整组物品并入 dp(原地更新 dp[0..m])。

    同体积物品取 k 个一定取价值最大的 k 个,所以组内降序后做前缀和 pre[k];
    k 超过组内个数时常数延拓 = 取价值 0 的幽灵物品,因 dp 单调不减而永不更优,
    于是窗口约束消失,转移简化为按 j mod s 拆链后的卷积。
    """
    values.sort(reverse=True)                 # 组内价值降序 => pre 凹
    m = len(dp) - 1
    k_max = m // s                            # 链上最多取 k_max 个(i - t <= k_max)
    pre = [0] * (k_max + 1)
    acc = 0
    for k in range(1, k_max + 1):
        if k <= len(values):
            acc += values[k - 1]
        pre[k] = acc                          # k > 组内个数时保持常数(延拓)

    for r in range(min(s, m + 1)):            # 余数 r 的链:容量 r, r+s, r+2s, ...
        dp[r::s] = chain(dp[r::s], pre)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)

    groups: dict[int, list[int]] = {}         # 体积 -> 该体积的所有物品价值
    for _ in range(n):
        s = next(data)
        v = next(data)
        if s <= m:                            # 体积超过容量上限,任何答案都用不到
            groups.setdefault(s, []).append(v)

    dp = [0] * (m + 1)                        # dp[j]:容量 <= j 时的最大价值
    for s in sorted(groups):
        use_group(dp, groups[s], s)

    sys.stdout.write(' '.join(map(str, dp[1:])) + '\n')


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 02:28
 * update_at: 2026-10-08 02:28
 */
// main.cpp:一本通 1786《01背包》
//
// 题意:n 个物品(体积 s、价值 v),对每个容量 j = 1..m **各自独立**做一次 0/1 背包,
//       输出 m 个最大价值。范围 1<=n<=1e6, 1<=m<=1e5, 1<=s<=300, 1<=v<=1e9。
//
// 朴素 01 背包是 O(n*m) = 1e11,超时。突破口是体积只有 300 种:
//   把物品按体积 s 分组,组内按价值降序取前 K 个(K = min(组内物品数, m/s)),
//   记前缀和 pre[k] = 该组价值最大的 k 个之和;取 k 个必然取价值最大的 k 个。
//   于是 dp[j] = 容量不超过 j 的最大价值,按组递推:
//       new_dp[j] = max{ dp[j-k*s] + pre[k] : 0 <= k <= j/s }
//   注:这里 k 允许超过组内物品数 cnt —— pre[k] = pre[cnt](取价值 0 的幽灵物品),
//   因为 dp 单调不减,取幽灵物品永不更优,故把 pre 常数延拓是**无损**的,可省掉窗口约束。
//   固定余数 r = j mod s 后,链上下标 i(j = r + i*s)互相独立:
//       new[i] = max{ f[t] + pre[i-t] : 0 <= t <= i }
//   pre 是凹函数(增量 v[k] 单调不增),故任意两个决策点 t1 < t2 的优劣只会反转一次,
//   argmax 关于 i 单调不减 —— 用分治优化(决策单调性)把一条链降到 O(L log L)。
//   总复杂度 sum_{s=1..300} O(m log(m/s)) ≈ 3e8 次简单运算(限时 7000 ms)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXS = 300;         // 题面给出的体积上界
const int MAXM = 100000;      // 题面给出的容量上界

ll dp[MAXM + 1];              // dp[j]:容量不超过 j 时的最大价值,题面答案即 dp[1..m]
ll f[MAXM + 1];               // 当前同余链上转移前的旧值 f[i] = dp[r + i*s]
ll g[MAXM + 1];               // 当前同余链上转移后的新值
ll pre[MAXM + 1];             // pre[k]:当前体积组内价值最大的 k 个物品的价值之和
int cnt[MAXS + 1];            // cnt[s]:体积为 s 的物品个数
vector<int> buck[MAXS + 1];   // buck[s]:体积为 s 的所有物品价值

// 分治优化:求解链上区间 [l, r] 的 g[],已知 opt(i)(最优决策 t)落在 [optl, optr] 内。
// 决策 t 的含义是"从旧链的下标 t 转移过来",即本组取了 i - t 个物品。
void solve(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    int lo = optl;                 // 下界:opt 单调不减
    int hi = min(optr, mid);       // 上界:t 不能超过 mid
    ll best = LLONG_MIN;
    int bestt = lo;
    for (int t = lo; t <= hi; t++) {
        ll cand = f[t] + pre[mid - t];
        if (cand > best) { best = cand; bestt = t; }
    }
    g[mid] = best;
    solve(l, mid - 1, optl, bestt);
    solve(mid + 1, r, bestt, optr);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int s, v;
        cin >> s >> v;
        if (s > m) continue;       // 任何容量都装不下,直接丢弃
        if (s < 1) continue;
        buck[s].push_back(v);      // s <= 300 由题面保证
    }

    for (int s = 1; s <= min(MAXS, m); s++) {
        if (buck[s].empty()) continue;
        sort(buck[s].begin(), buck[s].end(), greater<int>());  // 组内价值降序
        int c = (int)buck[s].size();
        int K = m / s;                                        // 链上最多取 K 个(i-t <= K)
        pre[0] = 0;
        for (int k = 1; k <= K; k++)                          // k>c 时常数延拓
            pre[k] = pre[k - 1] + (k <= c ? buck[s][k - 1] : 0);
        for (int r = 0; r < s; r++) {                         // 按余数拆成 s 条链
            if (r > m) break;
            int L = (m - r) / s;                              // 链长:i = 0..L
            for (int i = 0; i <= L; i++) f[i] = dp[r + i * s];
            solve(0, L, 0, L);
            for (int i = 0; i <= L; i++) dp[r + i * s] = g[i];
        }
    }

    for (int j = 1; j <= m; j++) {
        if (j > 1) cout << ' ';
        cout << dp[j];
    }
    cout << '\n';
    return 0;
}

复杂度

  • 时间:O(n+mlog⁡m+∑s=1300mlog⁡(m/s))O\big(n + m\log m + \sum_{s=1}^{300} m \log(m/s)\big),量级约 3×1083\times10^8 次简单运算。
  • 空间:O(n+m)O(n + m)(分组存储 + 若干长度 mm 的全局数组),约十几 MB。

总结

  1. 先找"种类数少"的特征。 本题 nn 高达 10610^6 但 s⩽300s \leqslant 300,把物品按体积 分组后,“取几个"取代了"取哪些”,问题立刻从物品维度降到体积维度。
  2. 单调 + 前缀和 = 可拆链。 同余类分组是背包类 DP 的常用解耦手段, 把二维 dp[j]dp[j] 摊平成 300300 条一维链。
  3. 凹性 ⇒ 决策单调。 降序排序后的前缀和天然凹,任意两个决策点的优劣只反转一次, 于是分治优化 / 单调队列都可以用。这里分治写法最短,且常数小。
  4. 反过来看,如果 ss 没有上界,这题就是 O(nm)=1011O(nm) = 10^{11} 的不可做题; 数据的特殊限制往往就是算法的入口。

备注

  • 本题素材源自带数据生成脚本(data.py),说明 data/ 是自造的;题面也可能是 从网络重建而来,出题意图与官方原题可能存在偏差,此处如实注明。
  • 时间限制 7000 ms、空间限制 512 MB。Python 侧同样算法在同阶复杂度下常数较大, 最大规模点会接近(但不超)时限;C++ 侧仅需数十毫秒,故以 C++ 作为正式解。