资源分配模型 (背包 DP)

算法简介

资源分配模型（即背包 DP）主要解决 在有限资源限制下，如何选择物品以达到目标最优 的一类问题。核心思想是将“资源”作为 DP 的状态（容量），枚举“物品”的选择策略进行转移。

• 时间复杂度：通常为 $O(N \cdot V)$，其中 $N$ 为物品数量，$V$ 为资源总量。
• 基本枚举顺序：通常先枚举物品 $i$，再枚举资源容量 $j$，最后枚举决策。

---

一、基础背包模型

1.1 0/1 背包 & 1.2 完全背包

这是所有背包问题的基石。区别在于每种物品是 仅有一件 还是 有无限件。

• 0/1 背包：容量 $j$ 必须 从大到小 (倒序) 枚举，防止同物品被重复累加。
• 完全背包：容量 $j$ 必须 从小到大 (正序) 枚举，利用已更新的状态实现叠加。

// 通用模板：根据题意选择内层循环方向
for (int i = 1; i <= n; i++) {
    // 【0/1 背包】：倒序
    for (int j = V; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
    /* // 【完全背包】：正序
    for (int j = w[i]; j <= V; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
    */
}

1.3 多重背包 (基础)

每种物品有数量限制 $c_i$。最基础的做法是将其展开为 $c_i$ 个 0/1 背包物品直接求解（若 $c_i$ 很大请参考第三部分的二进制拆分优化）。

for (int i = 1; i <= n; i++) {
    // 基础展开：死算，复杂度 O(V * Σc_i)
    for (int k = 1; k <= c[i]; k++) { 
        for (int j = V; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
}

1.4 分组背包

物品被分为 $K$ 组，每组 最多选 1 件。核心在于 组内决策互斥，组间独立。

for (int k = 1; k <= groups; k++) { // 1. 枚举组
    for (int j = V; j >= 0; j--) {  // 2. 枚举容量 (倒序)
        for (auto item : group[k]) { // 3. 枚举组内物品
            if (j >= item.w) 
                dp[j] = max(dp[j], dp[j - item.w] + item.v);
        }
    }
}

---

二、资源分配模型 (背包模型进阶)

【核心辨析】 资源分配 vs 传统背包

在进阶题目中，“背包”往往非常抽象，不再是“往包里塞东西”。我们需要建立如下映射：

• 传统背包：物品是实体的（如苹果），资源是物理的（如体积、重量）。
• 资源分配：物品是 “策略” 或 “操作”，资源是 “限制条件”（如时间、步数、修改次数）。

举例说明：[CSP-J 2022] 上升点列

• 问题：给定 $n$ 个点，可以自由添加 $k$ 个点，求最长上升点列。
• 转化：
  • 资源 (背包容量)：我们可以自由添加点的次数 $k$。
  • 物品 (消耗)：连接两个原有点 $P_i$ 和 $P_j$ 所需要的中间空缺距离 $d$（即曼哈顿距离 - 1）。
  • 价值：点列长度增加了 $d+1$。
• 区别：这里没有“装进包里的物品”，只有“消耗 $k$ 值来换取连接”的决策。

---

三、背包常见优化

3.1 二进制拆分 (多重背包优化)

当物品数量 $c_i$ 很大时，将 $c_i$ 拆解为 $1, 2, 4, \dots, 2^k, \text{余数}$。任意 $\le c_i$ 的数量都可由这些组合而成，从而转化为 $O(N \log C \cdot V)$ 的 0/1 背包。

// 二进制拆分核心逻辑
vector<int> weights, values;
for (int i = 1; i <= n; i++) {
    int count = c[i], k = 1;
    while (k <= count) {
        weights.push_back(k * w[i]);
        values.push_back(k * v[i]);
        count -= k;
        k *= 2;
    }
    if (count > 0) { // 处理余数
        weights.push_back(count * w[i]);
        values.push_back(count * v[i]);
    }
}
// 之后对 weights/values 做一次标准 0/1 背包即可

3.2 维度交换 (值域优化)

针对 求最值 问题，当容量 $V$ 极大 ($10^9$) 但价值较小 ($10^5$) 时，交换 DP 的下标与值。定义 $dp[v]$ 为获得价值 $v$ 的 最小消耗。

// 初始化：dp[0] = 0, 其他为 INF
memset(dp, 0x3f, sizeof(dp)); 
dp[0] = 0;

for (int i = 1; i <= n; i++) {
    for (int j = max_val_sum; j >= v[i]; j--) {
        dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
    }
}
// 统计：从大到小找满足 dp[i] <= 背包容量的最大 i

3.3 Bitset 优化 (可行性)

针对 可行性 问题，当数据范围极大 ($N \cdot V \approx 10^8$) 时，利用位运算并行处理状态转移。

#include <bitset>
bitset<100005> dp;
dp[0] = 1;

for (int i = 1; i <= n; i++) {
    dp |= (dp << w[i]); // 一行代码完成所有转移
}

3.4 贪心排序优化

针对 物品选择顺序影响结果 的问题（如含截止时间、高度限制、函数复合），先推导不等式排序，消除动态变量。

struct Item { int a, b; };
// 示例：ABC366 F (函数复合最大值)
bool cmp(Item x, Item y) {
    return (x.a - 1) * y.b > (y.a - 1) * x.b; // 推导出的不等式
}

sort(items.begin(), items.end(), cmp);
// 排序后进行 DP

【前置衔接知识点】
1、动态规划基础

【思维导图】

【题目知识点分类】