核心概述
快速背包聚焦在不同约束（0/1、完全、多重、值域小等）下用滚动数组与结构化优化降低时间与空间复杂度的通用实现方案。
原文引述
Description: Optimized knapsack solvers (0/1, complete, bounded) using rolling arrays (O(W) space) and value‑domain optimization (O(nV)). Supports divide‑and‑conquer and monotone queue for specific constraints.（摘自本节点现有英文注释） Time: 0/1 O(nW), Complete O(nW), Bounded O(nW log maxCnt) or O(nV) if value domain small（摘自本节点现有英文注释） Status: tested（摘自本节点现有英文注释）
展开阐述
-
定义与背景
- 面向容量上界 W 与物品集的背包问题族，通过状态压缩（O(W)）与针对性约束优化（如按值域 DP 到 O(nV)）以降低开销。
- 约束类型：0/1（每件至多一次）、完全（可无限次）、多重（数量受限）、值域小（按价值 DP）。
-
接口/状态与语义（依本仓库节点风格）
- 状态定义：dp[j] 为容量 j 下的最优值（或最小重量，按问题语义选 max/min）。
- 更新策略：
- 0/1 背包：j 从 W 到 w[i] 逆序，避免同一物品重复使用。
- 完全背包：j 从 w[i] 到 W 顺序，允许重复使用。
- 多重背包：数量 cnt[i] 进行二进制拆分后当作若干 0/1 物品处理。
- 值域优化：若价值总和 Vmax 小，改用 dp[v] 表示达成价值 v 的最小重量，返回满足 dp[v] ≤ W 的最大 v。
- 初始化：常见为 dp[0]=0，其余按语义置为 -∞ 或 +∞。
-
核心流程与关键要点
- 滚动数组：一维 dp 将空间降至 O(W)，注意遍历方向与覆盖关系。
- 二进制拆分：将 cnt 拆为 1,2,4,… 的组合，减少转移次数。
- 结构化优化：在同权或单调结构时可分治/单调队列进一步加速。
- 数值注意：价值可能溢出时使用 long long。
-
示例片段
- 0/1 背包（滚动数组）
for (int i = 0; i < n; ++i) {
for (int j = W; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}- 完全背包（顺序遍历）
for (int i = 0; i < n; ++i)
for (int j = w[i]; j <= W; ++j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);-
复杂度与边界
- 0/1 与完全：O(nW)；多重：O(nW log maxCnt)；值域小：O(nV)。
- 边界检查确保 j-w[i] ≥ 0。
-
适用场景与扩展
- 经典背包、容量受限选择；价值域受限问题用值域优化更优。
- 可结合分组与数据结构（如线段树）对转移进行批量或区间优化（见关联节点）。