发帖
雷达卡
课程内容概览
- 01背包
- 01背包优化——滚动数组
- 完全背包
- 完全背包优化——滚动数组
- 多重背包——转换为01背包
- 多重背包——二进制优化
- 混合背包——转换为01背包
- 混合背包——二进制优化
- 背包问题对比分析
- 课程总结
一、01背包问题解析
核心概念：
给定 N 个物品和一个容量为 M 的背包，每个物品仅能选取一次。第 i 个物品的重量为 W[i]，价值为 C[i]。目标是选出一组物品装入背包，使其总价值最大。
动态规划思路：
定义二维数组 dp[i][j] 表示从前 i 个物品中选择，放入容量为 j 的背包所能获得的最大价值。
状态转移公式：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - W[i]] + C[i])
该式表示：对于第 i 个物品，可以选择不放入（继承前 i-1 个的结果），或放入（需腾出空间并加上其价值）中的较优方案。
参考实现代码：
#include<bits/stdc++.h>
using namespace std;
int W[35], C[35];
int dp[35][205];
int main()
{
int M, N;
cin >> M >> N;
for (int i = 1; i <= N; i++)
{
cin >> W[i] >> C[i];
}
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
if (j >= W[i])
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + C[i]);
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[N][M];
return 0;
}
二、01背包的空间优化：滚动数组法
优化原理说明：
观察发现，状态 dp[i][j] 只依赖于上一层 i-1 的数据，因此可以将二维数组压缩为一维，使用 dp[j] 来表示当前轮次下容量 j 对应的最大价值。
为何采用逆序遍历？
在更新 dp[j] 时，必须确保 dp[j - W[i]] 尚未被本轮更新，即仍保留的是上一轮（i-1 层）的状态。通过从大到小遍历容量 j，可避免覆盖旧值，从而保证状态转移正确。
优化后代码示例：
#include<bits/stdc++.h>
using namespace std;
int W[35], C[35];
int dp[205];
int main()
{
int M, N;
cin >> M >> N;
for (int i = 1; i <= N; i++)
{
cin >> W[i] >> C[i];
}
for (int i = 1; i <= N; i++)
{
for (int j = M; j >= 1; j--)
{
if (j >= W[i])
{
dp[j] = max(dp[j], dp[j - W[i]] + C[i]);
}
}
}
cout << dp[M];
return 0;
}
三、完全背包问题详解
问题描述：
存在 N 种物品与一个容量为 M 的背包，每种物品数量无限。第 i 种物品的重量为 W[i]，价值为 C[i]。要求在不超过背包容量的前提下，使装入物品的总价值最大化。
与01背包的关键区别：
同一物品可多次选取，因此状态转移时允许基于当前层已更新的状态继续累加选择。
状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j - W[i]] + C[i])
注意此处第二项使用的是 dp[i][j - W[i]] 而非 dp[i-1][...]，表示可以在本轮重复选择该物品。
// 多重背包问题的处理方法：转化为01背包 // 问题描述 给定 N 种物品和一个容量为 M 的背包。第 i 种物品最多有 S[i] 件可用，每件的重量为 W[i]，价值为 C[i]。 目标是选择若干物品放入背包中，使得总价值最大。 // 核心思想 将多重背包中的每一种物品按照数量拆分，变成多个独立的单个物品，从而将其转换为标准的 01 背包问题进行求解。 例如，若某种物品有 3 件，则视为三个相同的独立物品分别考虑。// 实现方式 使用一个计数器记录拆分后的总物品数量，并将每个拆分出的物品单独存储其重量与价值。 #include<bits/stdc++.h> using namespace std; int price[10005], value[10005]; // 存储拆分后各物品的重量和价值 int dp[10005]; // 动态规划数组，用于01背包计算 int main() { int n, m, cnt = 1; // n: 物品种类数；m: 背包容量；cnt: 拆分后物品编号 cin >> n >> m; for (int i = 0; i < n; i++) { int v, m_val, s; // v: 单件重量；m_val: 单件价值；s: 可用数量 cin >> v >> m_val >> s; // 将该种类的 s 件物品逐一拆分为独立个体 while (s--) { price[cnt] = v; // 记录当前拆分物品的重量 value[cnt] = m_val; // 记录当前拆分物品的价值 cnt++; // 编号递增 } } cnt--; // 调整为实际的物品总数（因最后多加了一次） // 此处可继续执行01背包的状态转移过程（未完整写出） }
四、完全背包的空间优化：滚动数组法
核心原理说明：
在完全背包问题中，由于每个物品可以被多次选取，因此在状态更新时需要确保之前的状态已经包含了当前物品的使用情况。为此，在使用一维数组优化时，必须采用正向遍历容量的方式。
优化优势：
通过将二维 DP 数组压缩为一维，空间复杂度由 O(N×M) 降低至 O(M)，显著减少内存占用，同时保持逻辑一致性。
关键点解析：
- 使用 dp[j] 表示当前容量 j 下能获得的最大价值。
- 内层循环对容量从 1 到 M 正序遍历，以保证 dp[j - W[i]] 是本轮（即包含第 i 个物品）已更新过的状态，从而允许重复选择同一物品。
示例代码实现
#include<bits/stdc++.h>
using namespace std;
int W[35], C[35]; // 存储每个物品的重量和价值
int dp[205]; // 一维DP数组，表示不同容量下的最大价值
int main()
{
int M, N; // M: 背包总容量；N: 物品总数
cin >> M >> N;
// 输入每个物品的重量和价值
for (int i = 1; i <= N; i++)
{
cin >> W[i] >> C[i];
}
// 完全背包 + 滚动数组优化的核心流程
for (int i = 1; i <= N; i++) // 遍历每种物品
{
for (int j = 1; j <= M; j++) // 正序遍历背包容量
{
if (j >= W[i]) // 若当前容量可容纳该物品
{
// 状态转移方程：取不选或选该物品后的较大值
// 注意此处使用 dp[j - W[i]] 是当前轮可能已更新的状态
dp[j] = max(dp[j], dp[j - W[i]] + C[i]);
}
else // 容量不足，无法放入
{
dp[j] = dp[j]; // 状态不变
}
}
}
// 输出最终能获得的最大价值
cout << "max=" << dp[M];
return 0;
}
原始完全背包解法（二维DP）
该方法基于动态规划的经典二维模型，定义 dp[i][j] 为前 i 个物品在容量为 j 时所能达到的最大价值。
算法步骤详解
- 初始化输入：读取背包容量 M 和物品数量 N。
- 依次输入每个物品的重量 W[i] 和价值 C[i]。
- 双重循环：
- 外层控制物品索引 i（从 1 到 N）
- 内层控制背包容量 j（从 1 到 M）
- 状态转移条件判断：
- 若当前容量 j ≥ 第 i 个物品的重量 W[i]，则可以选择是否放入；
此时状态转移为：dp[i][j] = max(dp[i-1][j], dp[i][j-W[i]] + C[i])
注意这里使用的是dp[i][j-W[i]]，而非 01 背包中的dp[i-1][...]，表示允许重复选择。 - 否则不能放入，直接继承前 i-1 个物品的结果：
dp[i][j] = dp[i-1][j]
- 若当前容量 j ≥ 第 i 个物品的重量 W[i]，则可以选择是否放入；
完整参考代码
#include<bits/stdc++.h>
using namespace std;
int W[35], C[35];
int dp[35][205];
int main()
{
int M, N;
cin >> M >> N;
for (int i = 1; i <= N; i++)
{
cin >> W[i] >> C[i];
}
// 动态规划主循环
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
if (j >= W[i])
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - W[i]] + C[i]);
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
cout << "max=" << dp[N][M];
return 0;
}
六、多重背包——二进制优化
知识点：二进制优化原理
将物品的数量 S 拆分为若干组，每组数量为 1, 2, 4, ..., 2^k，最后一组为剩余部分 S - (2^(k+1)-1)。
通过这样的拆分方式，可以组合出任意不超过 S 的数量，从而用更少的物品组等效替代原物品。
优化效果：
原本有 S 件相同物品时需进行 S 次处理，经过二进制拆分后仅需 logS 个新物品即可表示所有可能情况，显著降低时间复杂度。
示例代码如下：
#include<bits/stdc++.h>
using namespace std;
int price[10005], value[10005];
int dp[10005];
int main()
{
int n, m, cnt = 1;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int v, w, s;
cin >> v >> w >> s;
// 二进制拆分过程
for (int k = 1; k <= s; k *= 2)
{
price[cnt] = k * v;
value[cnt] = k * w;
s -= k;
cnt++;
}
// 处理剩余未被完全拆分的部分
if (s > 0)
{
price[cnt] = s * v;
value[cnt] = s * w;
cnt++;
}
}
cnt--; // 调整为实际有效的物品总数
// 使用01背包方法求解
for (int i = 1; i <= cnt; i++)
{
for (int j = m; j >= price[i]; j--)
{
dp[j] = max(dp[j], dp[j - price[i]] + value[i]);
}
}
cout << dp[m];
return 0;
}
七、混合背包——统一转换为01背包
知识点：混合背包问题定义
当背包中包含多种类型的物品——有的只能选一次（01背包），有的可选无限次（完全背包），有的有数量限制（多重背包）——这类问题称为混合背包问题。
处理思路：
将所有类型物品统一转化为01背包中的独立物品：
- 对于01背包类物品，直接作为一个单独物品加入；
- 对于完全背包类物品，视作数量极多的多重背包，再通过特定方式拆解；
- 对于多重背包类物品，采用二进制优化拆分为多个01背包物品；
最终整个问题转化为标准01背包问题求解。
示例代码实现：
#include<bits/stdc++.h>
using namespace std;
int weight[1005], value[1005];
int dp[1005];
int main()
{
int n, m, cnt = 1;
cin >> m >> n;
for (int i = 0; i < n; i++)
{
int w, c, p;
cin >> w >> c >> p;
if (p == 0) // 完全背包处理：视为数量足够多
{
p = m / w; // 最多能放多少个
while (p--)
{
weight[cnt] = w;
value[cnt] = c;
cnt++;
}
}
else // 01背包或多重背包：每个物品逐个展开
{
while (p--)
{
weight[cnt] = w;
value[cnt] = c;
cnt++;
}
}
}
// 统一按01背包求解
for (int i = 1; i <= cnt; i++)
{
for (int j = m; j >= weight[i]; j--)
{
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[m]; // 输出最大价值
return 0;
}
// 记录物品的价值
value[cnt] = c;
// 物品数量计数器递增
cnt++;
}
// 结束物品遍历后，修正物品总数（因循环末尾多加了一次）
cnt--;
// 统一采用01背包的方式进行最终求解
// 遍历所有经过优化处理后的物品
for (int i = 1; i <= cnt; i++)
{
// 对背包容量进行逆序遍历，从最大容量m开始逐步减少
for (int j = m; j >= weight[i]; j--)
{
// 若当前容量足以容纳该物品
if (j >= weight[i])
{
// 应用01背包的状态转移公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
else
{
// 容量不足时，状态保持不变
dp[j] = dp[j];
}
}
}
// 输出在容量限制下所能获得的最大价值
cout << dp[m];
return 0;
}
八、混合背包问题——基于二进制的优化策略
核心知识点
优化思路： 针对多重背包部分，利用二进制拆分思想将多个相同物品组合成若干组，每组数量为2的幂次（如1, 2, 4, 8...），从而将物品总数显著减少，提升算法运行效率。
综合处理方式： - 01背包类物品：直接作为一个独立物品加入。 - 完全背包类物品：按最多可装入的数量（m/w）进行二进制拆分处理。 - 多重背包类物品：根据给定数量p，使用二进制方法拆分为多个组合物品。
示例代码实现
#include<bits/stdc++.h>
using namespace std;
int weight[10005], value[10005]; // 存储拆分后各组合物品的重量与价值
int dp[10005]; // 动态规划数组，表示容量为j时的最大价值
int main()
{
int n, m, cnt = 1; // cnt用于记录优化后物品的总数量，初始为1便于后续索引操作
cin >> m >> n; // 输入背包总容量m和物品种类数n
// 循环读取每种类型的物品信息
for (int i = 0; i < n; i++)
{
int w, c, p; // w:单个物品重量，c:单个物品价值，p:物品类型或数量标识
cin >> w >> c >> p;
// 完全背包处理（p == 0 表示无限供应）
if (p == 0)
{
p = m / w; // 计算理论上最多可放入多少件该物品
// 使用二进制拆分策略进行分解
for (int k = 1; k <= p; k *= 2)
{
weight[cnt] = k * w; // 组合后的总重量
value[cnt] = k * c; // 组合后的总价值
cnt++; // 物品计数器增加
p -= k; // 减去已处理的数量
}
// 若仍有剩余数量未被拆分，则单独作为一组处理
if (p > 0)
{
weight[cnt] = p * w;
value[cnt] = p * c;
cnt++;
}
}
// 01背包处理（p == 1 表示仅有一件）
else if (p == 1)
{
weight[cnt] = w;
value[cnt] = c;
cnt++;
}
// 多重背包处理（p > 1 表示有有限件）
else
{
// 同样采用二进制方式进行拆分
for (int k = 1; k <= p; k *= 2)
{
weight[cnt] = k * w;
value[cnt] = k * c;
cnt++;
p -= k;
}
// 处理拆分后剩下的部分
if (p > 0)
{
weight[cnt] = p * w;
value[cnt] = p * c;
cnt++;
}
}
}
// 调整物品总数，因最后多执行了一次cnt++
cnt--;
// 所有物品均已转化为01背包形式，统一求解
for (int i = 1; i <= cnt; i++)
{
// 逆序遍历背包容量，确保每个物品只被选择一次
for (int j = m; j >= weight[i]; j--)
{
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[m]; // 输出在容量m下能获得的最大价值
return 0;
}
九、各类背包问题对比分析
| 背包类型 | 物品数量限制 | 容量遍历顺序 | 常用优化手段 | 时间复杂度 |
|---|---|---|---|---|
| 01背包 | 每种物品仅一件 | 逆序遍历 | 滚动数组优化 | O(N×M) |
| 完全背包 | 每种物品数量无限 | 顺序遍历 | 滚动数组优化 | O(N×M) |
| 多重背包 | 每种物品数量有限 | 逆序遍历 | 二进制拆分优化 | O(N×logS×M) |
| 混合背包 | 多种类型共存 | 分类分别处理 | 综合优化策略 | O(N×logS×M) |
核心差异说明
- 01背包：采用逆序遍历是为了防止同一物品被重复选取，保证每个物品最多使用一次。
- 完全背包：使用顺序遍历允许状态由更小容量的状态转移而来，从而实现物品的多次选择。
- 多重背包：通过将有限数量的物品按二进制方式拆分成多个组合物品，转化为多个01背包问题来处理。
实际应用场景指导
在解决动态规划相关问题时，应根据题目中对物品选取次数的具体限制，合理选择对应的背包模型。准确识别模型类型有助于选用正确的遍历方式与优化技巧，显著提高解题效率与代码性能。
十、课程总结回顾
01背包是所有背包问题的基础模型，其特点是每件物品只能选择一次，求解时需对背包容量进行逆序遍历，以避免重复更新。
完全背包则允许物品被多次选取，在状态转移过程中应对容量进行顺序遍历，从而支持连续选取同一种物品。
在面对更加复杂的现实问题时，往往需要结合多种背包特性，灵活运用拆分、转化与优化技巧，构建高效的解决方案。
掌握各类背包问题的状态转移方程与遍历顺序，对于竞赛解题具有重要意义。其中，多重背包问题可以通过对物品数量进行拆分，转化为01背包的形式进行求解。
为了提升计算效率，常采用二进制优化策略，将物品按2的幂次进行分组拆分，从而大幅减少状态数量。而对于混合背包问题，则需根据每类物品的不同特性进行分类处理，结合01背包、完全背包和多重背包的解决方法，灵活运用多种优化技巧以达到最优效果。
京公网安备 11010802022788号
