算法课堂笔记：最小生成树与背包问题

---

一、最小生成树算法

最小生成树（MST）是在一个带权无向连通图中，找出一棵包含所有顶点且边权之和最小的树。

---

1.1 Kruskal 算法

算法思路

将所有边按权值从小到大排序，利用并查集贪心地选择最小权值且不构成环的边，直到选出 $n-1$ 条边为止。

时间复杂度

• 排序：$O(m\log m)$，$m$ 为边数。
• 并查集操作：每条边至多两次 find，近乎 $O(m\cdot \alpha(n))$，$\alpha(n)$ 为反阿克曼函数，可视为常数。
• 总体复杂度：$O(m\log m)$，适合稀疏图。

执行流程

1. 所有边按权值升序排序。
2. 初始化并查集，每个顶点自成一个集合。
3. 依次遍历每条边 $(u,v,w)$：
   • 若 $u$ 和 $v$ 不在同一集合，则选择该边，累加权值，合并集合。
   • 否则跳过。
4. 当选够 $n-1$ 条边时停止，即得到最小生成树。

C++ 代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1005;      // 最大顶点数
const int MAXM = 200005;    // 最大边数

struct Edge {
    int u, v, w;
    bool operator < (const Edge &e) const {
        return w < e.w;     // 按边权从小到大排序
    }
} edges[MAXM];

int parent[MAXN];

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);   // 路径压缩
    return parent[x];
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) parent[rx] = ry;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);

    // 初始化并查集
    for (int i = 1; i <= n; ++i) parent[i] = i;

    // 按边权排序  O(m log m)
    sort(edges, edges + m);

    int sum = 0, cnt = 0;
    for (int i = 0; i < m; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        // 若两端点不在同一集合，则加入该边
        if (find(u) != find(v)) {
            unite(u, v);
            sum += w;
            cnt++;
            if (cnt == n - 1) break;   // 已选够 n-1 条边
        }
    }

    printf("%d\n", sum);
    return 0;
}

---

1.2 Prim 算法

算法思路

从任意起点开始，逐步扩展生成树：每次从已选顶点集合到未选顶点的所有边中，选一条权值最小的边，将对应顶点加入。

时间复杂度

• 朴素实现（邻接矩阵，无堆优化）：每次找最小 $dist$ 需 $O(n)$，执行 $n$ 次，总 $O(n^2)$，适合稠密图。
• 若采用二叉堆优化可达到 $O(m\log n)$。

执行流程

1. 任选起点 $s$，$dist[s]=0$，其余 $dist$ 初始化为无穷大。
2. 用布尔数组标记顶点是否已加入 MST。
3. 循环 $n$ 次：
   • 在所有未访问顶点中选出 $dist$ 最小的顶点 $u$，标记为已访问，累加 $dist[u]$。
   • 用 $u$ 到邻居 $v$ 的边权更新 $dist[v]$（若边权更小）。
4. 所有顶点访问完后即得到最小生成树的权和。

C++ 代码（邻接矩阵， $O(n^2)$）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int g[MAXN][MAXN];     // 邻接矩阵
int dist[MAXN];        // dist[i] 表示 i 到当前生成树的最小边权
bool vis[MAXN];        // 标记是否已加入生成树

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= n; ++i) g[i][i] = 0;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        if (w < g[u][v]) g[u][v] = g[v][u] = w;   // 处理重边，保留最小权值
    }

    memset(vis, 0, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;          // 选择顶点 1 作为起点
    int sum = 0;

    for (int i = 1; i <= n; ++i) {
        // 选出未访问顶点中 dist 最小的
        int u = -1, minD = INF;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && dist[j] < minD) {
                minD = dist[j];
                u = j;
            }
        if (u == -1) break;       // 图不连通
        vis[u] = true;
        sum += minD;

        // 用 u 更新邻居的 dist 值
        for (int v = 1; v <= n; ++v)
            if (!vis[v] && g[u][v] < dist[v])
                dist[v] = g[u][v];
    }

    printf("%d\n", sum);
    return 0;
}

---

二、背包问题（二维动态规划）

本节所有背包模型均采用二维 DP 实现，状态定义为 $dp[i][j]$，不涉及滚动数组优化，便于理解转移逻辑。

---

2.1 多重背包（二进制优化）

问题描述

有 $N$ 种物品，第 $i$ 种物品体积为 $v_i$、价值 $w_i$、数量 $c_i$。背包容量为 $V$，每种物品可选不超过 $c_i$ 件，求总价值最大。

二进制优化原理

将数量为 $c$ 的物品拆成若干件，使其可以组合出 $0\sim c$ 中任意整数：

• 拆分方法：$1,2,4,\dots,2^{k-1},r$，其中 $r=c-(2^k-1)$ 且 $r<2^k$。
• 例如 $c=13$，拆成 $1,2,4,6$，可以凑出 $0\sim 13$。
• 正确性：前 $k$ 个二次幂能表示 $0\sim 2^k-1$，加上余数 $r$ 后范围连续扩展至 $c$。

时间复杂度

• 拆分后物品总件数 $M=\sum O(\log c_i)$。
• 二维 0/1 背包 DP：$O(M\cdot V)$。
• 总体复杂度：$O(V \sum \log c_i)$，远优于朴素 $O(V\sum c_i)$。

执行流程

1. 对每种物品按照二进制拆分成多个新物品（每个视为独立的 0/1 物品）。
2. 设拆分后的总物品数为 $M$。
3. 定义 $dp[i][j]$ 表示前 $i$ 个物品、容量为 $j$ 时的最大价值。
4. 转移方程（0/1 背包）：$$dp[i][j] = \max(dp[i-1][j],\; dp[i-1][j-v_i] + w_i) \quad (j \ge v_i)$$
5. 答案为 $dp[M][V]$。

C++ 代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_ITEMS = 2005;    // 拆分后最大物品数
const int MAXV = 2005;         // 最大背包容量

int vol[MAX_ITEMS], val[MAX_ITEMS]; // 拆分后的体积与价值
int dp[MAX_ITEMS][MAXV];            // dp[i][j] 前 i 件，容量 j

int main() {
    int N, V;
    scanf("%d%d", &N, &V);
    int cnt = 0;   // 拆分后物品总数

    for (int i = 0; i < N; ++i) {
        int v, w, c;
        scanf("%d%d%d", &v, &w, &c);
        // 二进制拆分
        int k = 1;
        while (c >= k) {
            ++cnt;
            vol[cnt] = v * k;
            val[cnt] = w * k;
            c -= k;
            k <<= 1;
        }
        if (c > 0) {
            ++cnt;
            vol[cnt] = v * c;
            val[cnt] = w * c;
        }
    }

    // 二维 0/1 背包 DP
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i - 1][j];   // 不选第 i 个物品
            if (j >= vol[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - vol[i]] + val[i]);
        }
    }

    printf("%d\n", dp[cnt][V]);
    return 0;
}

---

2.2 分组背包

问题描述

物品被划分为若干组，每组最多只能选一件物品。给定每件物品的体积与价值，求容量 $V$ 内的最大价值。

时间复杂度

• 设组数为 $T$，第 $g$ 组物品数为 $s_g$。
• DP 需要对每组复制上一组状态 $O(T\cdot V)$，以及枚举物品更新 $O(V\sum s_g)$。
• 总体复杂度：$O(V\cdot N)$，$N$ 为物品总数。

执行流程

1. 组编号为 $1\sim T$。
2. 定义 $dp[g][j]$ 表示考虑前 $g$ 组，容量为 $j$ 的最大价值。
3. 初始化 $dp[0][j]=0$。
4. 对于第 $g$ 组：
   • 先复制上一组状态：$dp[g][j] = dp[g-1][j]$（本组不选）。
   • 枚组内每件物品 $(v,w)$，用上一组的状态更新：$$dp[g][j] = \max(dp[g][j],\; dp[g-1][j-v] + w) \quad (j \ge v)$$
5. 答案为 $dp[T][V]$。

核心要点：更新时始终使用 $dp[g-1][...]$，保证每组最多只选一件。

C++ 代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_T = 105;          // 最大组数
const int MAXV = 2005;          // 最大容量
const int MAX_ITEMS = 105;      // 每组最大物品数

int groupV[MAX_T][MAX_ITEMS], groupW[MAX_T][MAX_ITEMS];
int groupSize[MAX_T];
int dp[MAX_T][MAXV];            // dp[g][j] 前 g 组，容量 j

int main() {
    int T, V;
    scanf("%d%d", &T, &V);
    for (int g = 1; g <= T; ++g) {
        scanf("%d", &groupSize[g]);
        for (int k = 1; k <= groupSize[g]; ++k)
            scanf("%d%d", &groupV[g][k], &groupW[g][k]);
    }

    // 初始化第 0 组
    for (int j = 0; j <= V; ++j) dp[0][j] = 0;

    for (int g = 1; g <= T; ++g) {
        // 先继承上一组状态（本组一件都不选）
        for (int j = 0; j <= V; ++j)
            dp[g][j] = dp[g - 1][j];

        // 再考虑选本组中的某一件
        for (int k = 1; k <= groupSize[g]; ++k) {
            int v = groupV[g][k], w = groupW[g][k];
            for (int j = v; j <= V; ++j)
                dp[g][j] = max(dp[g][j], dp[g - 1][j - v] + w);
        }
    }

    printf("%d\n", dp[T][V]);
    return 0;
}

---

2.3 混合背包

问题描述

背包容量为 $V$，物品有三种类型：

• 0/1 物品：最多选 1 次。
• 完全物品：可选无限次。
• 多重物品：有数量上限 $c$。

求最大总价值。

时间复杂度

• 将多重物品二进制拆分为多个 0/1 物品，设最终总物品阶段数为 $M$。
• 二维 DP 对每个阶段遍历容量 $V$，复杂度 $O(M\cdot V)$。
• $M \approx N + \sum \log c_i$，因此总体 $O(V\cdot (N + \sum \log c_i))$。

执行流程

1. 读取物品时，将多重物品按二进制拆分成 0/1 物品；0/1 物品和完全物品保留类型标记。
2. 统一编号为 $1\sim M$，记录 $kind[i]$：0 表示 0/1，1 表示完全。
3. 定义 $dp[i][j]$ 表示考虑前 $i$ 个阶段、容量 $j$ 的最大价值。
4. 状态转移：
   • 0/1 物品：$dp[i][j] = \max(dp[i-1][j],\; dp[i-1][j-v_i] + w_i)$
   • 完全物品：$dp[i][j] = \max(dp[i-1][j],\; dp[i][j-v_i] + w_i)$
5. 答案为 $dp[M][V]$。

C++ 代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_ITEMS = 2005;    // 最终总物品数上限
const int MAXV = 2005;         // 最大容量

int vol[MAX_ITEMS], val[MAX_ITEMS], kind[MAX_ITEMS];
// kind[i] = 0 表示 0/1 物品， kind[i] = 1 表示完全物品
int dp[MAX_ITEMS][MAXV];

int main() {
    int N, V;
    scanf("%d%d", &N, &V);
    int cnt = 0;   // 统一编号

    for (int i = 0; i < N; ++i) {
        int v, w, t;
        scanf("%d%d%d", &v, &w, &t);  // t: 0-0/1, 1-完全, >1-多重数量
        if (t == 0) {
            ++cnt;
            vol[cnt] = v;  val[cnt] = w;  kind[cnt] = 0;
        } else if (t == 1) {
            ++cnt;
            vol[cnt] = v;  val[cnt] = w;  kind[cnt] = 1;
        } else {
            // 多重物品进行二进制拆分，均转为 0/1 物品
            int k = 1;
            while (t >= k) {
                ++cnt;
                vol[cnt] = v * k;
                val[cnt] = w * k;
                kind[cnt] = 0;
                t -= k;
                k <<= 1;
            }
            if (t > 0) {
                ++cnt;
                vol[cnt] = v * t;
                val[cnt] = w * t;
                kind[cnt] = 0;
            }
        }
    }

    // 二维 DP
    for (int i = 1; i <= cnt; ++i) {
        if (kind[i] == 0) {   // 0/1 物品
            for (int j = 0; j <= V; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j >= vol[i])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - vol[i]] + val[i]);
            }
        } else {               // 完全物品
            for (int j = 0; j <= V; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j >= vol[i])
                    dp[i][j] = max(dp[i][j], dp[i][j - vol[i]] + val[i]);
            }
        }
    }

    printf("%d\n", dp[cnt][V]);
    return 0;
}

---

总结

• Kruskal：$O(m\log m)$，排序+并查集，适合稀疏图。
• Prim（朴素）：$O(n^2)$，邻接矩阵，适合稠密图。
• 多重背包（二进制优化）：$O(V\sum \log c_i)$，将数量拆成二次幂组合。
• 分组背包：$O(V\cdot N)$，每组至多选一件，依赖上一组状态。
• 混合背包：多重部分拆分后，与 0/1、完全物品统一二维 DP，复杂度 $O(V\cdot M)$。