---

🎒 背包问题拓展整理

---

✅ 一、混合背包（0-1 / 完全 / 多重的混合）

📌 问题描述

给定若干种物品，每种物品有一个“类型”：

• 0-1背包：只能选一次
• 完全背包：可以无限选
• 多重背包：最多选 $s_i$ 次

🧠 状态设计

• $f[j]$：容量不超过 $j$ 的最大价值

🔄 状态转移

根据类型不同分类讨论：

• 0-1 背包：

  for (int j = m; j >= w; j--)
      f[j] = max(f[j], f[j - w] + v);
  

• 完全背包：

  for (int j = w; j <= m; j++)
      f[j] = max(f[j], f[j - w] + v);
  

• 多重背包（朴素写法）：

  for (int k = 1; k <= s; k++)
      for (int j = m; j >= k * w; j--)
          f[j] = max(f[j], f[j - k * w] + k * v);
  

  优化：可以使用 二进制拆分法 或 单调队列优化 降低复杂度。

---

✅ 二、分组背包（Group Knapsack）

📌 问题描述

有 $n$ 个物品，划分成 $g$ 组。每组最多选一个物品。

🧠 状态设计

• $f[j]$：容量不超过 $j$ 的最大价值（组数隐含在更新顺序中）

🔄 状态转移

for (int i = 1; i <= g; i++) // 枚举每组
{
    for (int j = m; j >= 0; j--) // 倒序容量，确保每组最多取一个
    {
        for (auto [w, v] : group[i]) // 枚举组内物品
        {
            if (j >= w)
                f[j] = max(f[j], f[j - w] + v);
        }
    }
}

🧱 数据存储

vector<array<int, 2>> group[1005]; // group[i] 表示第 i 组的所有物品

---

✅ 三、有依赖的背包（依赖树背包 / 树形背包）

📌 问题描述

有些物品是主件，必须选主件才能选附件（主从依赖关系，可构成一棵树）。

🧠 状态设计

• $f[u][j]$：以 $u$ 为根的子树，容量不超过 $j$ 的最大价值

🔄 状态转移

• 对于每个节点 $u$，先处理其所有子节点 $v$，再进行背包合并：

void dfs(int u)
{
    for (int j = cost[u]; j <= m; j++) // 至少要放得下自己
        f[u][j] = value[u];

    for (int v : children[u])
    {
        dfs(v);
        for (int j = m; j >= cost[u]; j--) // 倒序容量
            for (int k = 0; k <= j - cost[u]; k++) // 分配给子节点的容量
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
    }
}

🌳 处理主从结构

• 构建树结构（如：$v$ 附属于 $u$，则 $v$ 是 $u$ 的儿子）

---

✅ 四、二维费用背包（Two-dimensional Knapsack）

📌 问题描述

每个物品有两种代价：$a_i$ 和 $b_i$，总容量限制为 $(A, B)$。

🧠 状态设计

• $f[i][j]$：第一维消耗 $i$，第二维消耗 $j$ 时的最大价值

🔄 状态转移

0-1版本：

for (int i = A; i >= a; i--)
    for (int j = B; j >= b; j--)
        f[i][j] = max(f[i][j], f[i - a][j - b] + v);

完全版本：

for (int i = a; i <= A; i++)
    for (int j = b; j <= B; j++)
        f[i][j] = max(f[i][j], f[i - a][j - b] + v);

---

✅ 总结对比表

类型	限制	状态设计	转移方式
混合背包	物品类型混合	$f[j]$	分类型处理
分组背包	每组最多选一个物品		遍历组内更新
有依赖背包	子物品依赖主物品（树结构）	$f[u][j]$	DFS合并
二维费用背包	每个物品有两个维度的消耗	$f[i][j]$	双层循环转移

---