C语言动态规划背包问题全解：01、完全、多重（二进制拆分）与分组
本文深入解析C语言中的动态规划算法，详细覆盖01背包、完全背包、多重背包（含二进制拆分优化）及分组背包四类经典模型。通过对比二维数组与一维滚动数组的写法，揭示状态转移的核心差异，并提供完整的C语言代码实现与复杂度分析。
01背包问题
01背包是动态规划中最基础的问题模型。给定 $N$ 件物品和一个容量为 $V$ 的背包，每件物品只有一个（0或1），第 $i$ 件物品的体积是 $v[i]$，价值是 $w[i]$。目标是选择装入背包的物品，使得总价值最大且总体积不超过背包容量。
状态定义： 设 $f[i][j]$ 表示只考虑前 $i$ 件物品，当背包容量为 $j$ 时能获得的最大价值。
第1步：理解二维状态转移
对于第 $i$ 件物品，在容量 $j$ 下有两种决策：
- 不选第 $i$ 件物品：价值等于前 $i-1$ 件物品在容量 $j$ 下的最大价值，即 $f[i-1][j]$。
- 选第 $i$ 件物品（仅当 $j \ge v[i]$ 时）：价值为前 $i-1$ 件物品在剩余容量 $j-v[i]$ 下的最大价值加上当前物品价值，即 $f[i-1][j-v[i]] + w[i]$。
综合上述逻辑，递推公式为：
if(j < v[i]) f[i][j] = f[i - 1][j]; else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
完整二维实现代码如下：
#includeusing namespace std; const int MAXN = 1005; int v[MAXN], w[MAXN], f[MAXN][MAXN]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { if(j < v[i]) f[i][j] = f[i - 1][j]; else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; }
第2步：一维数组空间优化
观察发现，$f[i][j]$ 仅依赖于上一行 $f[i-1]$ 的数据。因此可以使用一维数组 $f[j]$ 代替二维数组，将空间复杂度从 $O(NV)$ 降至 $O(V)$。关键技巧在于内层循环逆序枚举，确保更新 $f[j]$ 时使用的是上一轮（未包含当前物品）的数据。
一维压缩后的核心循环如下：
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
完整的一维实现代码：
#includeusing namespace std; const int MAXN = 1005; int f[MAXN]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { int v, w; cin >> v >> w; // 边输入边处理 for(int j = m; j >= v; j--) f[j] = max(f[j], f[j - v] + w); } cout << f[m] << endl; return 0; }
完全背包问题
完全背包与01背包的区别在于：每种物品有无数件可用。这意味着如果选择了第 $i$ 件物品，在计算下一状态时仍然可以考虑再次选择它。
第1步：暴力与思路推导
最直观的方法是增加一个循环 $k$ 来枚举选取第 $i$ 种物品的数量，时间复杂度较高。但我们可以观察状态转移规律：
- $f[i][j] = max( f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, ... )$ • $f[i][j-v] = max( f[i-1][j-v], f[i-1][j-2v]+w, ... )$
对比两式，可以发现 $f[i][j-v]$ 已经包含了“在当前容量下尽可能多选”的最优子结构。因此可以推导出更简洁的递推式：
f[i][j] = max(f[i-1][j], f[i][j-v[i]] + w[i]);
第2步：一维化与正向遍历
与01背包相比，唯一的不同是将依赖项从 $f[i-1][j-v[i]]$（上一轮数据）变成了 $f[i][j-v[i]]$（本轮已更新的最新数据）。这对应到一维数组时，只需要将**内层循环改为从小到大正序枚举**即可。
最终优化后的完全背包代码：
#includeusing namespace std; const int N = 1010; int f[N], v[N], w[N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i]; // 注意：内层循环从 v[i] 开始递增遍历 for(int i = 1; i <= n; i++) for(int j = v[i]; j <= m; j++) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }
多重背包问题
多重背包规定每件物品只有有限数量 $s[i]$。解决策略分为朴素转换和优化两种。
第1步：多重背包 I（朴素拆分法）
可以将第 $i$ 件物品拆分成 $s[i]$ 个独立的单件物品，从而转化为 01 背包问题求解。
代码如下，虽然逻辑清晰，但在数据量大时容易超时：
// 拆分部分逻辑示意
for(ll i=1; i<=n; i++) {
cin >> a >> b >> c;
for(ll j=1; j<=c; j++) {
v[cnt] = a; w[cnt] = b; cnt++;
}
}
// 随后执行标准的 01 背包逻辑
第2步：多重背包 II（二进制拆分优化）
为什么能优化？
任何整数 $S$ 都可以由若干系数为 1 的二进制数组合而成（如 $13 = 1 + 4 + 8$）。通过将数量为 $S$ 的物品按 $1, 2, 4, 8...$ 进行打包，可以将物品的数量级从 $O(S)$ 降低到 $O(rac{ ext{lg} S}{1})$。
例如，若物品数量为 13，拆分为 1, 2, 4, 6 四个新物品。无论原物品取多少个（0~13），都能通过这些组合物的特定组合来表示。这样将多重背包转化为了物品种类稍多但总数可控的 01 背包问题。
二进制拆分代码实现：
int cnt = 0; // 将物品重新分组后的顺序
for (int i = 1; i <= n; i ++)
{
int a, b, s; // a 体积, b 价值, s 每种物品的个数
scanf("%d %d %d", &a, &b, &s);
int k = 1; // 二进制拆分基数
while (k <= s)
{
cnt ++;
v[cnt] = a * k; // 每组的体积
w[cnt] = b * k; // 每组的价值
s -= k;
k *= 2;
}
if (s > 0) // 剩下的归入新的一组
{
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt; // 更新物品总数
拆分完成后，直接套用前面的 01 背包模板即可高效求解。
分组背包问题
分组背包中，所有物品被划分为 $N$ 组，每组内的物品相互冲突，每组最多只能选择一个物品。
第1步：状态定义与计算
设 $f[i][j]$ 表示从前 $i$ 组中选，且总体积不超过 $j$ 的最大价值。 根据集合划分的思想，对于第 $i$ 组，我们需要枚举该组选的哪个物品（或者都不选）：
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
其中 $k$ 遍历第 $i$ 组中的所有物品索引。
第2步：代码实现
初始化时需将数组清零（全局变量自动为零）。由于状态转移仅依赖第 $i-1$ 层的数据，同样可以进行一维空间优化。在优化为一维数组时，需要注意先倒序枚举体积 $j$，再正序枚举组内物品 $k$，以保证同一组物品只被选取一次且不干扰同体积的其他组内物品决策。
#includeusing namespace std; const int N=110; int f[N], v[N][N], w[N][N], s[N]; int n,m; int main(){ cin>>n>>m; for(int i=0;i >s[i]; for(int j=0;j >v[i][j]>>w[i][j]; } // 分组背包模板 for(int i=0;i=0;j--){ // 枚举体积j（必须逆序，同01背包） for(int k=0;k = v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } } } cout<
以上就是C语言动态规划多种背包问题分析讲解的详细内容，更多关于C语言动态规划背包问题的资料请关注本站其它相关文章！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
