体积只有 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
形式化题目
有
数据规模:
记
朴素做法对每个 for j: for i: dp=...,
复杂度
正解
思路
第一步:按体积分组。
体积只有
于是每组内把价值降序排序,做前缀和
(第
关键性质:因为价值已降序,增量
pre[k] - pre[k-1] = $ 组内第 $k 大价值单调不增, 所以是凹函数(离散意义下增量单调不增)。
第二步:按组做一次“完全背包式”的整组转移。
设当前
这就是一个“同一种物品可重复取、但第
第三步:固定余数,拆成独立链。
(1) 式里
则 (1) 变成
下标
第四步:决策单调性 + 分治优化。
(2) 式对固定
所以 argmax
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)每条链长度
总复杂度:
在 7000 ms 限时下 C++ 可以过(
细节: 体积
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:
,量级约 次简单运算。 - 空间:
(分组存储 + 若干长度 的全局数组),约十几 MB。
总结
- 先找"种类数少"的特征。 本题
高达 但 ,把物品按体积 分组后,“取几个"取代了"取哪些”,问题立刻从物品维度降到体积维度。 - 单调 + 前缀和 = 可拆链。 同余类分组是背包类 DP 的常用解耦手段,
把二维
摊平成 条一维链。 - 凹性 ⇒ 决策单调。 降序排序后的前缀和天然凹,任意两个决策点的优劣只反转一次, 于是分治优化 / 单调队列都可以用。这里分治写法最短,且常数小。
- 反过来看,如果
没有上界,这题就是 的不可做题; 数据的特殊限制往往就是算法的入口。
备注
- 本题素材源自带数据生成脚本(
data.py),说明data/是自造的;题面也可能是 从网络重建而来,出题意图与官方原题可能存在偏差,此处如实注明。 - 时间限制 7000 ms、空间限制 512 MB。Python 侧同样算法在同阶复杂度下常数较大, 最大规模点会接近(但不超)时限;C++ 侧仅需数十毫秒,故以 C++ 作为正式解。