背包问题综合笔记

---

📖 目录

1. 01 背包
2. 完全背包
3. 多重背包
4. 二维费用背包
5. 分组背包
6. 混合背包
7. 滚动数组优化总表

---

1. 01 背包

问题
有 $N$ 件物品，背包容量 $V$。第 $i$ 件物品费用 $c_i$，价值 $w_i$。
每件物品最多选 1 次，求最大总价值。

状态定义
dp[i][v]：前 $i$ 件物品，容量为 $v$ 时的最大价值。

转移方程

$$dp[i][v] = \max(dp[i-1][v],\ dp[i-1][v - c_i] + w_i) \quad (v \ge c_i)$$

---

✦ 二维 DP（原始）

int c[MAXN], w[MAXN];          // 费用、价值，下标从 1 开始
int dp[MAXN][MAXV];            // dp[i][v]

for (int i = 1; i <= N; ++i) {
    for (int v = 0; v <= V; ++v) {
        dp[i][v] = dp[i - 1][v];           // 不选第 i 件
        if (v >= c[i])
            dp[i][v] = max(dp[i][v], dp[i - 1][v - c[i]] + w[i]);
    }
}
// 答案：dp[N][V]

✦ 滚动数组优化（一维）

空间 $O(V)$
关键：容量必须 ◀ 逆序 枚举，保证 dp[v - c[i]] 来自上一轮 $i-1$。

int dp[MAXV] = {0};
for (int i = 1; i <= N; ++i) {
    // ▼ 逆序遍历容量
    for (int v = V; v >= c[i]; --v) {
        dp[v] = max(dp[v], dp[v - c[i]] + w[i]);
    }
}
// 答案：dp[V]

---

2. 完全背包

问题
每件物品可以选无限次，其余同 01 背包。

转移方程（二维）

$$dp[i][v] = \max(dp[i-1][v],\ dp[i][v - c_i] + w_i) \quad (v \ge c_i)$$

与 01 背包的区别：选择物品 $i$ 时，状态来自同一行的 dp[i][v-c_i]。

---

✦ 二维 DP

int dp[MAXN][MAXV];
for (int i = 1; i <= N; ++i) {
    for (int v = 0; v <= V; ++v) {
        dp[i][v] = dp[i - 1][v];           // 不选
        if (v >= c[i])
            dp[i][v] = max(dp[i][v], dp[i][v - c[i]] + w[i]); // 同行转移
    }
}

✦ 滚动数组优化（一维）

关键：容量 ▶ 正序 枚举，使 dp[v - c[i]] 恰好是本轮已更新的状态，实现无限次。

int dp[MAXV] = {0};
for (int i = 1; i <= N; ++i) {
    // ▼ 正序遍历容量
    for (int v = c[i]; v <= V; ++v) {
        dp[v] = max(dp[v], dp[v - c[i]] + w[i]);
    }
}

---

3. 多重背包

问题
第 $i$ 件物品最多可选 $m_i$ 次。

---

✦ 朴素二维 DP（三重循环）

int m[MAXN];                  // 物品的最多选择次数
int dp[MAXN][MAXV];

for (int i = 1; i <= N; ++i) {
    for (int v = 0; v <= V; ++v) {
        dp[i][v] = dp[i - 1][v];                  // 一件不选
        for (int k = 1; k <= m[i] && k * c[i] <= v; ++k) {
            dp[i][v] = max(dp[i][v],
                dp[i - 1][v - k * c[i]] + k * w[i]);
        }
    }
}

---

✦ 二进制拆分 + 滚动数组（推荐）

核心思想：将 $m_i$ 拆成 $1, 2, 4, \dots, 2^{k-1}, r$，使任意 $0 \sim m_i$ 的选择都能被组合。
每拆出一份，立即用 01 背包逆序 处理，无需额外数组。

int dp[MAXV] = {0};
for (int i = 1; i <= N; ++i) {
    int cost = c[i], value = w[i], num = m[i];
    // 二进制拆分，边拆边处理
    for (int k = 1; k <= num; k <<= 1) {        // k = 1,2,4,...
        int cur_cost = cost * k;
        int cur_value = value * k;
        // ▼ 逆序（当作 01 背包物品）
        for (int v = V; v >= cur_cost; --v)
            dp[v] = max(dp[v], dp[v - cur_cost] + cur_value);
        num -= k;
    }
    if (num > 0) {                              // 剩余部分
        int cur_cost = cost * num;
        int cur_value = value * num;
        for (int v = V; v >= cur_cost; --v)
            dp[v] = max(dp[v], dp[v - cur_cost] + cur_value);
    }
}
// 答案：dp[V]

⏳ 时间复杂度 $O(V\sum \log m_i)$，空间 $O(V)$。

---

4. 二维费用背包

问题
每件物品有两种费用：$c_i$（花费 1）和 $d_i$（花费 2），上限分别为 $V$ 和 $U$。
物品为 01 型（只能选一次），求最大价值。
（完全 / 多重变种仅需调整循环方向）

状态定义
dp[i][v][u]：前 $i$ 件物品，两项费用分别不超过 $v$ 和 $u$ 的最大价值。

转移方程

$$dp[i][v][u] = \max(dp[i-1][v][u],\ dp[i-1][v - c_i][u - d_i] + w_i)$$

---

✦ 三维 DP（原始）

int c1[MAXN], c2[MAXN], w[MAXN];  // 两种费用及价值
int dp[MAXN][MAXV][MAXU];

for (int i = 1; i <= N; ++i) {
    for (int v = 0; v <= V; ++v) {
        for (int u = 0; u <= U; ++u) {
            dp[i][v][u] = dp[i - 1][v][u];   // 不选
            if (v >= c1[i] && u >= c2[i])
                dp[i][v][u] = max(dp[i][v][u],
                    dp[i - 1][v - c1[i]][u - c2[i]] + w[i]);
        }
    }
}
// 答案：dp[N][V][U]

✦ 滚动数组优化（二维 DP）

关键：因为是 01 型，两个容量维度 均需逆序 枚举。

int dp[MAXV][MAXU] = {0};
for (int i = 1; i <= N; ++i) {
    // ▼ 两维均逆序
    for (int v = V; v >= c1[i]; --v) {
        for (int u = U; u >= c2[i]; --u) {
            dp[v][u] = max(dp[v][u],
                dp[v - c1[i]][u - c2[i]] + w[i]);
        }
    }
}

变种提示

• 若为 完全背包：两个容量循环 均改为正序。
• 若为 多重背包：先二进制拆分，再按 01 型逆序处理。

---

5. 分组背包

问题
物品被分为 $K$ 组，每组最多选一件，组内物品互斥。

数据存储（纯数组）
grpCnt[k]：第 $k$ 组的物品数
grpCost[k][j]、grpValue[k][j]：第 $k$ 组第 $j$ 件物品的费用 / 价值

状态定义
dp[k][v]：考虑前 $k$ 组，容量为 $v$ 的最大价值。

---

✦ 二维 DP

int grpCnt[K+1];
int grpCost[K+1][MAX_ITEM];
int grpValue[K+1][MAX_ITEM];
int dp[K+1][V+1];

for (int k = 1; k <= K; ++k) {
    for (int v = 0; v <= V; ++v) {
        dp[k][v] = dp[k - 1][v];                  // 该组不选
        for (int j = 0; j < grpCnt[k]; ++j) {     // 尝试选组内一件
            int cost = grpCost[k][j];
            int value = grpValue[k][j];
            if (v >= cost)
                dp[k][v] = max(dp[k][v],
                    dp[k - 1][v - cost] + value);
        }
    }
}
// 答案：dp[K][V]

✦ 滚动数组优化（一维）

⚠️ 循环顺序至关重要：必须先 容量逆序，再内层遍历组内物品。

int dp[MAXV] = {0};
for (int k = 1; k <= K; ++k) {                   // 1. 枚举组
    for (int v = V; v >= 0; --v) {               // 2. ▼ 逆序容量
        for (int j = 0; j < grpCnt[k]; ++j) {    // 3. 枚举组内物品
            int cost = grpCost[k][j];
            int value = grpValue[k][j];
            if (v >= cost)
                dp[v] = max(dp[v], dp[v - cost] + value);
        }
    }
}

❌ 若将容量循环与组内物品循环互换，会变成组内物品可多选（退化为 01 背包）。

---

6. 混合背包

问题
同一题目中，物品可能具有不同类型：

• type = 0：01 背包
• type = 1：完全背包
• type = 2：多重背包（次数 $m[i]$）

策略：公用同一个 dp 数组，根据类型分别转移。

---

✦ 二维 DP（按类型处理）

int type[MAXN], m[MAXN];         // 类型与多重次数
int dp[MAXN][MAXV];

for (int i = 1; i <= N; ++i) {
    int cost = c[i], value = w[i];
    if (type[i] == 0) {          // 01 背包
        for (int v = 0; v <= V; ++v) {
            dp[i][v] = dp[i - 1][v];
            if (v >= cost)
                dp[i][v] = max(dp[i][v], dp[i - 1][v - cost] + value);
        }
    }
    else if (type[i] == 1) {     // 完全背包
        for (int v = 0; v <= V; ++v) {
            dp[i][v] = dp[i - 1][v];
            if (v >= cost)
                dp[i][v] = max(dp[i][v], dp[i][v - cost] + value);
        }
    }
    else if (type[i] == 2) {     // 多重背包（朴素 k 次）
        int cnt = m[i];
        for (int v = 0; v <= V; ++v) {
            dp[i][v] = dp[i - 1][v];
            for (int k = 1; k <= cnt && k * cost <= v; ++k)
                dp[i][v] = max(dp[i][v],
                    dp[i - 1][v - k * cost] + k * value);
        }
    }
}

---

✦ 滚动数组优化（一维，推荐）

多重背包部分采用边拆分边逆序处理，简洁高效。

int dp[MAXV] = {0};
for (int i = 1; i <= N; ++i) {
    int cost = c[i], value = w[i];
    if (type[i] == 0) {                    // 01 → 逆序
        for (int v = V; v >= cost; --v)
            dp[v] = max(dp[v], dp[v - cost] + value);
    }
    else if (type[i] == 1) {               // 完全 → 正序
        for (int v = cost; v <= V; ++v)
            dp[v] = max(dp[v], dp[v - cost] + value);
    }
    else if (type[i] == 2) {               // 多重 → 拆分 + 逆序
        int num = m[i];
        for (int k = 1; k <= num; k <<= 1) {
            int cur_cost = cost * k, cur_val = value * k;
            for (int v = V; v >= cur_cost; --v)
                dp[v] = max(dp[v], dp[v - cur_cost] + cur_val);
            num -= k;
        }
        if (num > 0) {
            int cur_cost = cost * num, cur_val = value * num;
            for (int v = V; v >= cur_cost; --v)
                dp[v] = max(dp[v], dp[v - cur_cost] + cur_val);
        }
    }
}

---

7. 滚动数组优化总表

背包模型	遍历顺序	空间形式	核心原因
01 背包	◀ 逆序	一维	dp[v-cost] 必须来自上一轮 $i-1$，避免重复选取
完全背包	▶ 正序		dp[v-cost] 来自本物品已更新状态，允许无限次
多重背包	拆分后 ◀ 逆序		每个子物品独立，等价于 01 背包
二维费用	两维同向	二维	01 型均逆序；完全型均正序
分组背包	容量 ◀ 逆序	一维	容量状态来自上一组，保证组内互斥
混合背包	按类型分别		共用数组，根据类型决定正/逆

---

🧠 记忆口诀

• “01 逆，完全顺，多重拆开再逆推”
• “分组先逆容，再枚举商品”
• “二维费用同进退，类型决定方向”

---

⚙️ 附加重点

初始化问题

• 求刚好装满背包的最大价值：dp[0] = 0，其余 dp[1..V] = -INF。
• 求可以不装满的最大价值：全部初始化为 0。

数组大小建议
根据题目约束，合理设定 MAXN、MAXV、MAXU 等宏。