【动态规划笔记】完全背包问题_背包问题 动态规划

问题

有 N 件物品和一个容量为 W 的背包，每件物品可无限选用。第 i 件物品的重量是 Ci，价值是 Vi。请问怎么往背包装物品，可使这些物品的重量总和不超过背包容量且价值总和最大。

分析一

问题类似 “01 背包问题”，不同于 “01 背包”中的每件物品只能选 1 件或 0 件，本题每件物品可选无限件，当然不会超过背包容量 W 的。
如果继续参考 “01 背包问题”解法，那么需要在状态转移方程中引入每件物品选了 k 件这个变量，如下：
dp[i][j]=max⁡k{dp[i−1][j−k⋅C[i]]+k⋅V[i]∣0≤k⋅C[i]≤j}dp[i][j] = \\max_{k} \\left\\{ dp[i-1][j - k \\cdot C[i]] + k \\cdot V[i] \\mid 0 \\leq k \\cdot C[i] \\leq j \\right\\}dp[i][j]=kmax​{dp[i−1][j−k⋅C[i]]+k⋅V[i]∣0≤k⋅C[i]≤j}

• $dp[i][j]$ 表示前 i 件物品放入容量为 j 的背包得到的最大价值；
• 初始化 $dp[0][j]=0$，$dp[i][0]=0$，没有物品选或背包容量是0，价值都是0；
• 公式以集合的方式定义，大括号左边是转移方程，右边是约束 k 的取值范围；
• 显然 $k$ 不可能超过当前背包容量 $j$ ，有人会问前 $i-1$ 件物品是不是也占用了背包容量，$k\ast C[i]$ 不可能装满背包。不是这样，因为每件物品可选择多件，因此当前容量为 $j$ 的背包完全可以只装第 i 件物品，如果第 $i$ 物品恰好装满了背包，那么状态转移到第 $i-1$件物品的最大价值是 $dp[i-1][0]$。
• 方程和“ 01 背包”一样有 N * W 个状态要求解，对于每个状态 $dp[i][j]$，$k$的取值范围是$[0,floor(j/C[i])]$，因此总的求解时间复杂度大致为 O(NW∗∑i⌊jC[i])O(NW * \\sum_i \\lfloor{\\frac{j}{C[i]}})O(NW∗∑i​⌊C[i]j​)，时间复杂度很大，需要改进。

优化一

• 若两件物品 $i$、$j$ 满足 $C[i]$ ≤ $C[j]$ 且 $V[i]$ ≥ $V[j]$，则将可以将物品 $j$ 直接去掉，不用考虑。任何情况下都可将价值小费用高的 $j$ 换成物美价廉的 $i$，得到的方案至少不会更差。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。

算法过程

1. 输入处理

   • 读取物品数量 N 和背包容量 W
   • 读取每件物品的重量数组 costs 和价值数组 values

2. 物品预处理

   • 将物品按价值升序排序（仅比较价值，不处理重量）
   • 遍历排序后的物品，若当前物品 i 的价值 ≥ 前一物品 i-1 且重量更小，则丢弃物品 i-1

3. 构建动态规划表

   • 创建二维数组 dp[i][j]，表示前 i 个物品放入容量为 j 的背包的最大价值
   • 三重循环填充 dp 表：
     • 外层循环遍历物品
     • 中层循环遍历背包容量
     • 内层循环遍历当前物品的选取次数（0到 j/costs[i-1]）

4. 输出结果

   • 返回 dp[N][W] 作为最大价值

复杂度分析

• 时间复杂度

  • 排序：O(N log N)
  • 预处理：O(N)
  • 动态规划：O(N × W × W)
    总体复杂度：O(N × W²)

• 空间复杂度

  • 动态规划表：O(N × W)
    总体复杂度：O(N × W)

参考代码

function solution() { let [N, W] = readline().split(\' \').map(Number); const costs = readline().split(\' \').map(Number); const values = readline().split(\' \').map(Number); let things = []; for (let i = 0; i < N; i++) { things[i] = [values[i], costs[i]]; } // 对物品按价值从小到大排序 things.sort((a, b) => a[0] - b[0]); const discardSet = new Set(); for (let i = 1; i < N; i++) { if (things[i][0] >= things[i-1][0]) { if (things[i][1] < things[i-1][1]) { discardSet.add(i-1); // 丢弃价值小成本大的物品 } } } costs.length = 0; values.length = 0; // 计算新的物品列表 for (let i = 0; i < things.length; i++) { if (discardSet.has(i)) continue; values.push(things[i][0]); costs.push(things[i][1]); } N = values.length; const dp = Array.from({ length: N+1}, () => Array(W+1).fill(0)); for (let i = 1; i <= N; i++) { for (let j = 1; j <= W; j++) { for (let k = 0; k * costs[i-1] <= j; k++) { // 计算选择0-k个物品的最大价值 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * costs[i-1]] + k * values[i-1]); } } } console.log(dp[N][W]);}/** * line0: 物品数量 N， 背包容量 W * line1: 每件物品的重量 C[i] * line2: 每件物品的价值 V[i] */const cases = [ `3 4 2 1 3 4 2 3 `,];let caseIndex = 0;let lineIndex = 0;const readline = (function () { let lines = []; return function () { if (lineIndex === 0) { lines = cases[caseIndex] .trim() .split(\"\\n\") .map((line) => line.trim()); } return lines[lineIndex++]; };})();cases.forEach((_, i) => { caseIndex = i; lineIndex = 0; solution();});

优化二

针对背包问题而言，比较不错的一种方法是：首先将费用大于 V 的物品去掉，然后使用类似计数排序的做
法，计算出费用相同的物品中价值最高的是哪个，可以 O(V + N) 地完成这个优化。

参考代码：

 ... // 步骤1: 费用分组优化 // 1.1 剔除费用超过W的物品，并记录每个费用对应的最大价值 const maxValueForCost = Array(W + 1).fill(0); // 初始化每个费用的最大价值为0 for (let i = 0; i < N; i++) { const c = costs[i]; const v = values[i]; if (c <= W && v > maxValueForCost[c]) { maxValueForCost[c] = v; } } // 1.2 生成优化后的物品列表 const filteredItems = []; for (let c = 1; c <= W; c++) { if (maxValueForCost[c] > 0) { filteredItems.push([maxValueForCost[c], c]); // [value, cost] } } // 更新物品数量和数组 N = filteredItems.length; filteredItems.forEach(([v, c], i) => { values[i] = v; costs[i] = c; }); ...

这种优化在费用范围较小且存在大量重复费用时效果显著，能将预处理时间从 O (N log N) 降至 O (N+W)，并减少动态规划处理的物品数量。

分析二

观察“01 背包问题”最终优化的状态转移方程：

for (let i = 0; i <= N; i++) { // 正序遍历每件物品for (let j = W; j >= costs[i]; j--) { // 倒序遍历背包容量，背包容量最小要大于等于当前物品的重量dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);}}

外层循环遍历每件物品，内层循环倒序遍历背包的容量，从最大的背包容量开始，dp[j] 表述容量为 j 的背包能取得的最大物品价值。在01背包问题中，倒序遍历背包容量是为了确保每个物品只被选择一次。这一设计与动态规划的状态转移逻辑密切相关。

状态转移方程的依赖关系

01背包的状态转移方程为：

dp[j] = max(dp[j], dp[j - costs[i]] + values[i])

其中，dp[j] 表示背包容量为 j 时的最大价值。该方程的含义是：

• 选择当前物品：背包容量需减少 costs[i]，价值增加 values[i]，即 dp[j - costs[i]] + values[i]
• 不选择当前物品：保持原有价值 dp[j]

关键问题：若正序遍历背包容量，dp[j - costs[i]] 可能已被当前物品更新过，导致重复选择。

正序遍历导致的重复选择问题

假设当前处理物品 i，若正序遍历背包容量 j 从 costs[i] 到 W：

• 当计算 dp[j] 时，dp[j - costs[i]] 可能已在本轮处理物品 i 时被更新（因 j - costs[i] < j）
• 这意味着物品 i 被多次选择，违反了01背包每个物品只能选一次的约束

示例：
物品 i 的费用为 2，价值为 3。若正序遍历：

• j = 2 时，dp[2] = max(dp[2], dp[0] + 3) = 3（选择了物品 i）
• j = 4 时，dp[4] = max(dp[4], dp[2] + 3)，此时 dp[2] 已被更新为选择物品 i 的结果，导致物品 i 被重复选择。

倒序遍历如何避免重复选择

倒序遍历背包容量 j 从 W 到 costs[i]：

• 当计算 dp[j] 时，dp[j - costs[i]] 是上一轮物品 i-1 的结果（因 j - costs[i] < j，且 j 从大到小遍历）
• 确保每个物品只在上一轮结果的基础上做选择，避免重复选择

示例：
仍以物品 i（费用2，价值3）为例，倒序遍历：

• j = 4 时，dp[4] = max(dp[4], dp[2] + 3)，此时 dp[2] 是上一轮的结果（未选物品 i）
• j = 2 时，dp[2] = max(dp[2], dp[0] + 3)，更新为选择物品 i 的结果
• 每个物品 i 仅被考虑一次。

”完全背包问题“允许物品数量无限选，因此需要正序遍历背包容量：

• 当计算 dp[j] 时，dp[j - costs[i]] 可能已包含当前物品 i 的选择
• 允许在当前物品的基础上继续选择，实现无限次选择的效果

状态转移方程：

dp[j] = max(dp[j], dp[j - costs[i]] + values[i]) // 正序遍历 j 从 costs[i] 到 W

由”01背包问题“的状态转移方程推出了 $O(NV)$ 时间复杂度的”完全背包问题“解法。

参考代码：

function solution() { let [N, W] = readline().split(\' \').map(Number); const costs = readline().split(\' \').map(Number); const values = readline().split(\' \').map(Number); let things = []; for (let i = 0; i < N; i++) { things[i] = [values[i], costs[i]]; } things.sort((a, b) => a[0] - b[0]); const discardSet = new Set(); for (let i = 1; i < N; i++) { if (things[i][0] >= things[i-1][0]) { if (things[i][1] < things[i-1][1]) { discardSet.add(i-1); } } } costs.length = 0; values.length = 0; for (let i = 0; i < things.length; i++) { if (discardSet.has(i)) continue; values.push(things[i][0]); costs.push(things[i][1]); } N = values.length; const dp = Array(W+1).fill(0); for (let i = 1; i <= N; i++) { const c = costs[i]; const v = values[i]; for (let j = c; j <= W; j++) { dp[j] = Math.max(dp[j], dp[j - costs[i]] + v); } } console.log(dp[W]);}/** * line0: 物品数量 N， 背包容量 W * line1: 每件物品的重量 C[i] * line2: 每件物品的价值 V[i] */const cases = [ `3 4 2 1 3 4 2 3 `,];let caseIndex = 0;let lineIndex = 0;const readline = (function () { let lines = []; return function () { if (lineIndex === 0) { lines = cases[caseIndex] .trim() .split(\"\\n\") .map((line) => line.trim()); } return lines[lineIndex++]; };})();cases.forEach((_, i) => { caseIndex = i; lineIndex = 0; solution();});