背包DP之完全背包

完全背包以“物品可无限选用”的特性区别于其他背包DP模型，它广泛应用于“不限数量的物品选择”场景——如“用无限硬币凑金额”“不限次数的物品采购”等。

一、完全背包基础认知

1.1 问题定义

给定n种物品，每种物品有重量w[i]和价值v[i]；背包容量为C。每种物品可选择无限次装入（完全背包的核心），求在总重量不超过C的前提下，能装入物品的最大总价值。

示例：

• 输入：n=2, C=5, w=[2,3], v=[3,5]
• 输出：8（选择1个重量2的物品和1个重量3的物品，总重量5，价值3+5=8；或3个重量2的物品总重量6超过容量，不合法）

1.2 核心特征

• 无限选用：每种物品可装入0次、1次、2次……直到总重量超过背包容量（区别于0/1背包的“最多1次”）。
• 容量约束：总重量≤C，与其他背包模型一致。
• 优化目标：最大化总价值，需在“数量选择”和“容量分配”间找到平衡。

完全背包的本质是“带容量约束的无限物品选择优化”，其解法是0/1背包的扩展，但因“无限选用”特性，遍历顺序和递推逻辑有显著差异。

二、完全背包的状态设计与递推

2.1 状态定义

沿用背包问题的经典状态设计，聚焦“物品数量”和“背包容量”：

• 设dp[i][j]表示“考虑前i种物品，背包容量为j时的最大价值”。
• 目标是dp[n][C]（考虑所有物品，容量C时的最大价值）。

2.2 递推关系

对于第i种物品，由于可无限选用，选择逻辑为：不选该物品或选1次、2次……直到重量超过j。

1. 不选第i种物品：价值与前i-1种物品相同 →
   dp[i][j] = dp[i-1][j]

2. 选第i种物品k次（k ≥ 1，且k×w[i] ≤ j）：
   价值 = 前i-1种物品在容量j - k×w[i]时的价值 + k×v[i] →
   dp[i][j] = max(dp[i][j], dp[i-1][j - k×w[i]] + k×v[i])

但直接枚举k会导致时间复杂度飙升（k最大为j/w[i]）。通过优化可简化为：

• 若选择至少1次第i种物品，等价于“先选1次，剩余容量仍可继续选该物品” →
  dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])
  （dp[i][j - w[i]]已包含“选0次、1次……”第i种物品的最优解）

2.3 关键：正序遍历容量

与0/1背包的“逆序遍历”不同，完全背包需正序遍历容量：

• 正序遍历确保dp[i][j - w[i]]已包含“当前物品被选择过”的状态，允许同一物品被多次选用。
• 遍历顺序：外层物品→内层容量（正序），确保每种物品可被无限次考虑。

三、代码实现

3.1 基础二维DP实现

public class UnboundedKnapsack {/*** 完全背包基础实现（二维DP）* @param n 物品种类数* @param C 背包容量* @param w 物品重量数组* @param v 物品价值数组* @return 最大价值*/public int maxValue(int n, int C, int[] w, int[] v) {// 二维DP数组：dp[i][j] = 前i种物品，容量j时的最大价值int[][] dp = new int[n + 1][C + 1];// 遍历每种物品（i从1到n）for (int i = 1; i <= n; i++) {int currW = w[i - 1]; // 当前物品重量（0基索引）int currV = v[i - 1]; // 当前物品价值// 遍历容量（正序：允许同一物品多次选择）for (int j = 0; j <= C; j++) {// 情况1：不选当前物品，价值继承前i-1种dp[i][j] = dp[i - 1][j];// 情况2：选当前物品（至少1次），需容量足够if (j >= currW) {dp[i][j] = Math.max(dp[i][j], dp[i][j - currW] + currV);}}}return dp[n][C];}public static void main(String[] args) {UnboundedKnapsack solver = new UnboundedKnapsack();int n = 2; // 2种物品int C = 5; // 容量5int[] w = {2, 3}; // 重量int[] v = {3, 5}; // 价值System.out.println(solver.maxValue(n, C, w, v)); // 输出8（2+3重量，3+5价值）}
}

3.2 空间压缩优化

观察二维DP可知，dp[i][j]仅依赖dp[i-1][j]（上一行）和dp[i][j - w[i]]（当前行左侧），可压缩为一维数组：

• 用dp[j]表示“当前处理到第i种物品，容量j时的最大价值”。
• 正序遍历容量，直接覆盖旧值（旧值对应“前i-1种物品”的状态）。

public int maxValueOptimized(int n, int C, int[] w, int[] v) {// 一维DP数组：dp[j] = 容量j时的最大价值（滚动更新）int[] dp = new int[C + 1];// 遍历每种物品for (int i = 0; i < n; i++) {int currW = w[i];int currV = v[i];// 正序遍历容量（关键：允许同一物品多次选择）for (int j = currW; j <= C; j++) { // j从currW开始（小于的容量无法选择）dp[j] = Math.max(dp[j], dp[j - currW] + currV);}}return dp[C];
}

优化说明：

• 空间复杂度从O(n×C)降至O(C)，适合n较大的场景。
• 正序遍历是核心：j从currW到C，确保dp[j - currW]已被当前物品更新（允许累计选择次数）。例如：
  • 处理j=4时，dp[4]可能已包含“选2次重量2的物品”（j=2时已更新为3，j=4时dp[2]+3=6）。

四、实例推演

4.1 输入数据

• 物品数n=2，容量C=5
• 物品1：w=2, v=3；物品2：w=3, v=5

4.2 一维DP更新过程

1. 初始状态：dp = [0,0,0,0,0,0]（未处理任何物品）。

2. 处理物品1（w=2, v=3）：

   • 正序遍历j=2→5：
     • j=2：dp[2] = max(0, dp[0]+3) = 3
     • j=3：j < 2×2（无法选2次），dp[3]保持0
     • j=4：dp[4] = max(0, dp[2]+3) = 3+3=6（选2次）
     • j=5：dp[5] = max(0, dp[3]+3) = 0+3=3（选1次，剩余容量1）
   • 处理后dp = [0,0,3,0,6,3]。

3. 处理物品2（w=3, v=5）：

   • 正序遍历j=3→5：
     • j=3：dp[3] = max(0, dp[0]+5) = 5（选1次）
     • j=4：j < 3？不，j=4 ≥3，dp[4] = max(6, dp[1]+5)=6（不变）
     • j=5：dp[5] = max(3, dp[2]+5) = 3+5=8（选1次物品2，搭配1次物品1）
   • 处理后dp = [0,0,3,5,6,8]。

4. 结果：dp[5] = 8（符合预期）。

五、完全背包的变种与应用

5.1 变种问题

1. 计数问题（完全背包方案数）：

   • 问题：求用无限物品装满容量C的方案数（如“硬币兑换I”）。
   • 解法：dp[j] += dp[j - w[i]]，初始化dp[0] = 1（空方案）。

2. 最小数量问题（完全背包最小值）：

   • 问题：求用无限物品装满容量C的最少物品数（如“硬币兑换II”）。
   • 解法：dp[j] = min(dp[j], dp[j - w[i]] + 1)，初始化dp[0] = 0，其他为+∞。

3. 多重背包（有限次数）：

   • 问题：物品可选用有限次（如最多k次），是完全背包与0/1背包的中间态。
   • 解法：通过“二进制拆分”将物品拆分为0/1背包的形式（如k=5拆分为1+2+2）。

5.2 应用场景

• 货币兑换：用无限硬币凑指定金额（如“最少硬币数”“兑换方案数”）。
• 资源采购：物品可无限采购，有限预算下最大化收益（如“采购零件组装设备”）。
• 生产规划：原材料无限，有限产能下最大化产品价值（如“用钢板切割零件”）。

六、时间复杂度与优化

6.1 时间复杂度

• 基础二维DP与优化一维DP的时间复杂度相同：O(n×C)（n为物品数，C为容量）。
• 当n=100，C=10^4时，总操作次数为100×10^4=10^6，效率可接受。

6.2 优化技巧

1. 物品剪枝：

   • 若物品A的重量≥物品B且价值≤物品B，则A为无效物品（选B更优），可删除A。
   • 例：A（w=5, v=3）和B（w=4, v=4），A可剪枝。

2. 容量上限优化：

   • 对每种物品，计算“单位重量价值”（v[i]/w[i]），优先处理高价值密度物品（启发式优化，不改变复杂度）。

3. 大数据优化（当C极大时）：

   • 若存在w=1的物品，可直接计算最大数量（C×v），避免遍历。
   • 结合数学公式：对单一物品，最大价值为(C//w)×v。

七、完全背包与0/1背包的核心区别

特性	0/1背包	完全背包
物品选择次数	每种最多1次	每种可无限次
容量遍历顺序	逆序（避免重复选择）	正序（允许多次选择）
递推依赖	依赖前i-1种物品状态	依赖当前i种物品状态
典型应用	物品不可重复选用场景	物品可无限选用场景

总结

完全背包以“物品可无限选用”为核心特征，其解法的关键是正序遍历容量——这允许同一物品被多次计入状态，与0/1背包的逆序遍历形成鲜明对比。掌握完全背包需注意：

1. 递推关系：dp[j] = max(dp[j], dp[j - w[i]] + v[i])（复用当前物品的状态）。
2. 遍历顺序：外层物品→内层容量（正序），确保无限选择逻辑。
3. 变种迁移：计数、最小值等问题可通过调整初始化和递推公式实现。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～