高效算法解析：背包问题的多维优化与实现

核心逻辑与数学原理

背包问题是一类典型的高维约束状态组合优化问题，其核心在于：在有限资源边界（背包容量 $V$）下，如何通过对离散决策（选或不选、选多少个）的阶段性扫描，使目标函数（总价值）达到极值。

三大核心背包模型的数学本质各异：

1. 01 背包 (01 Knapsack)：每种物品仅一件。决策具有二重性，状态转移依赖于上一阶段未受当前物品污染的纯净历史。
2. 完全背包 (Unbounded Knapsack)：每种物品无限件。决策具有连续性，状态转移依赖于当前阶段已加入当前物品的最新状态。
3. 多重背包 (Bounded Knapsack)：每种物品有固定件数限制 $C_i$。直接暴力拆分会导致复杂度退化为 $O(V \sum C_i)$。

• 二进制拆分优化：将数量 $C_i$ 拆解为累加和为 $C_i$ 的一组 2 的幂次幂项组合：$1, 2, 4, \dots, 2^k, C_i - (2^{k+1} - 1)$。由于任何小于等于 $C_i$ 的整数都能被这组基底唯一表示，多重背包被彻底降维映射为包含 $O(\log C_i)$ 个新物品的 01 背包，全局复杂度降至 $O(N \cdot V \log C)$。
• 单调队列优化：对于转移方程 $f[j] = \max_{0 \le k \le C_i} \{ f[j - k \cdot w_i] + k \cdot v_i \}$，根据容量对物品体积 $w_i$ 的余数进行同余分组：$j = r + q \cdot w_i$（其中 $0 \le r < w_i$）。方程在同一余数链上变形为：

$$f[r + q \cdot w_i] = \max_{q - C_i \le k \le q} \{ f[r + k \cdot w_i] - k \cdot v_i \} + q \cdot v_i$$

这是一个标准的滑动窗口最值问题，通过单调队列维护 $f[r + k \cdot w_i] - k \cdot v_i$ 的单调递减序列，可将状态转移耗时优化至 $O(1)$，全局复杂度降至极限的 $O(N \cdot V)$。

状态设计与算法推导

使用一维滚动数组压缩空间后，各类背包的状态空间、转移方程与循环序有着严密的几何逻辑：

1. 01 背包

• 方程：$f[j] = \max(f[j], f[j - w_i] + v_i)$
• 循环序：外层正序遍历物品 $i$，内层倒序遍历容量 $j$（从 $V$ 递减至 $w_i$）。
• 推导几何：倒序确保了在计算 $f[j]$ 时，所引用的前驱状态 $f[j - w_i]$ 尚未被第 $i$ 轮物品更新，它依然代表第 $i-1$ 阶段的净值，契合每件物品只能选一次的限制。

2. 完全背包

• 方程：$f[j] = \max(f[j], f[j - w_i] + v_i)$
• 循环序：外层正序遍历物品 $i$，内层正序遍历容量 $j$（从 $w_i$ 递增至 $V$）。
• 推导几何：正序使得在计算 $f[j]$ 时，若前驱状态 $f[j - w_i]$ 在当前轮已经被更新过（即已经放入过至少一件物品 $i$），当前状态可以在此基础上重复叠加，完美映射无限件的选择特性。

3. 多重背包二进制拆分

• 推导过程：设某物品数量为 $C$。令 $k = 1$，若 $C \ge k$，则切分出一个体积为 $k \cdot w$，价值为 $k \cdot v$ 的独立新物品，同时 $C = C - k, k = k \times 2$。重复此操作直到 $C < k$。若最终 $C > 0$，将剩余的 $C$ 独立包装为一个新物品。最后对所有拆分出的新物品跑标准 01 背包。

C++ 标准源码（NOIP风格）

以下源码在同一程序中给出 01 背包、完全背包与多重背包（二进制拆分）的一维高效工程实现。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXV = 20005; // 针对背容量
int f[MAXV];

// 用于多重背包拆分出来的扁平化物品结构
struct Item {
    int w, v;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, max_v;
    if (!(cin >> n >> max_v)) return 0;

    vector<Item> items;

    for (int i = 1; i <= n; ++i) {
        int w, v, c, type;
        cin >> w >> v >> c >> type; // type: 1->01, 2->完全, 3->多重

        if (type == 1) {
            items.push_back({w, v});
        } 
        else if (type == 2) {
            // 完全背包在后面单独用正序处理，此处由于需要统一调度，可暂不放入01队列
            // 考场为了代码高内聚，通常直接把三种背包合在主循环里拆分处理
        } 
        else if (type == 3) {
            // 多重背包：二进制拆分核心逻辑
            for (int k = 1; c >= k; k <<= 1) {
                items.push_back({k * w, k * v});
                c -= k;
            }
            if (c > 0) {
                items.push_back({c * w, c * v});
            }
        }
    }

    // ==================== 01背包 & 多重背包(拆分后) 的统一倒序驱动 ====================
    for (const auto& item : items) {
        for (int j = max_v; j >= item.w; --j) { // 致命踩坑点：必须严格逆序，否则退化为完全背包
            f[j] = max(f[j], f[j - item.w] + item.v);
        }
    }

    // ==================== 完全背包的独立正序驱动（假设单独读入了一组完全背包物品） ====================
    // 此处仅做示范：若物品是完全背包类型，循环必须改写为正序
    int comp_w = 5, comp_v = 10; // 模拟一个完全背包物品
    for (int j = comp_w; j <= max_v; ++j) { // 正序驱动，允许状态自我污染，承接多件
        f[j] = max(f[j], f[j - comp_w] + comp_v);
    }

    cout << f[max_v] << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 01 背包一维压缩时容量循环方向写反

• 现象：将 01 背包的容量循环写成了 for (int j = w[i]; j <= V; ++j)。代码可以通过编译，但输出结果极大。因为当计算后面的状态（如 $f[2w_i]$）时，它会读取前面刚刚在同一轮被更新过的 $f[w_i]$，从而导致一件物品被重复放入了多次，01 背包直接无端退化成了完全背包。
• 规避手段：牢记一维滚动数组的底层更新逻辑。01 背包必须逆序（从大到小），完全背包必须正序（从小到大）。

2. 多重背包二进制拆分时漏掉剩余尾数

• 现象：在进行二进制拆分时，循环条件写错或在退出循环后，忘记将剩余的 $C$（即 $C > 0$ 且 $C < k$ 的部分）打包放入物品集合，导致原物品总量缩水，算出的最大价值偏小。
• 规避手段：拆分完毕后，必须跟上 if (c > 0) items.push_back({c * w, c * v}); 这道严密的安检程序，保证原总量被无损拆分。

经典 NOIP/洛谷 真题

1. 洛谷 P1776 宝物筛选

• 题意描述：给定 $N$ 种宝物，每种宝物有价值 $v_i$、重量 $w_i$ 以及数量 $m_i$。现在有一个承重能力为 $W$ 的背包，求在不超出背包承重的情况下，能够装入宝物的最大总价值。$W \le 40000, N \le 100, m_i \le 100000$。
• 问题本质与解题思路：标准的多重背包问题。由于单种物品数量 $m_i$ 极高，暴力拆解会导致复杂度达到 $O(W \sum m_i)$ 从而彻底崩溃。
• 核心思路：使用二进制拆分。对每种宝物的数量 $m_i$ 进行按位切分，转换为 $\log m_i$ 个独立的 01 背包物品。拆分后，总物品件数缩减为 $N \log M \approx 100 \times 17 \approx 1700$ 件。对这 1700 件新物品运行标准的一维逆序 01 背包状态转移，总执行次数约为 $1.7 \times 10^3 \times 4 \times 10^4 = 6.8 \times 10^7$，可在 1 秒内轻松斩杀。

2. 洛谷 P1616 疯狂的采药

• 题意描述：给定背包总容量 $T$ 和 $M$ 种草药，每种草药可以无限制地采摘。已知每种草药的采摘时间 $t_i$ 和价值 $v_i$，求在规定时间内能获得的最大总价值。$T \le 10^7, M \le 10^4$。
• 问题本质与解题思路：完全背包的极限空间与时间压榨题。
• 核心思路：每种物品无限件，状态转移方程形式上与 01 背包一致，但空间迭代的方向必须切换为正序。
• 致命特判点：此题的数据范围极其恶毒（$T \le 10^7$）。如果定义二维状态数组必爆内存。一维状态数组 f 的大小必须开到 $10^7$ 级别。同时，由于价值叠加可能严重超出 32 位整型的上限，f 数组的类型以及存储最终答案的变量**必须声明为 long long，否则会在大数据点上由于整型溢出（Integer Overflow）直接变成负数。