资源分配型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 传统背包


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

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

* 问题：给定 $n$ 个点，可以自由添加 $k$ 个点，求最长上升点列。

* 转化：

* 资源 (背包容量)：我们可以自由添加点的次数 $k$。

* 物品 (消耗)：连接两个原有点 $P_i$ 和 $P_j$ 所需要的中间空缺距离 $d$（即曼哈顿距离 - 1）。

* 价值：点列长度增加了 $d+1$。

* 区别：这里没有“装进包里的物品”，只有“消耗 $k$ 值来换取连接”的决策。

三、背包常见优化

3.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 维度交换 (值域优化)

// 初始化：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 优化 (可行性)

#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