企业官网建设流程全解析

• 教程
• 文档

导读

背包问题（Knapsack Problem）是动态规划中最经典、最核心的模型之一，也是面试与竞赛中出现频率极高的考点。本指南以 LogicStack-LeetCode 仓库的 Index/背包 DP.md 索引为核心骨架，结合仓库内 279、322、416、494、518、879 等题目的完整题解源码，系统讲解「01 背包」「完全背包」「多维背包」「分组背包」等子模型的判别方法、状态定义、状态转移方程、滚动数组与一维空间优化技巧。读完本文，你将掌握一套「识别背包模型 → 设计状态 → 推导转移 → 优化空间」的通用解题流水线，并能直接对照仓库中每道题的 Java 实现进行验证与练习。

一、背包问题：一套可以复用的动态规划框架

1.1 什么是背包问题

背包问题的本质是一个组合优化问题：给定若干「物品」，每个物品有体积（成本）和价值（收益），要求在不超出背包容量的前提下，通过选择物品达到「全局最优」（最大价值 / 最小成本）或「特定状态」（恰好凑出某个值 / 凑出某个值的方案数）。

仓库题解中反复强调的一个判别习惯是（见 322. 零钱兑换（中等）.md）：

当看到题目是给定一些「物品」，让我们从中进行选择，以达到「最大价值」或者「特定价值」时，我们应该联想到「背包问题」。被选物品之间不需要满足特定关系，只需要选择物品，以达到「全局最优」或者「特定状态」即可。

1.2 如何根据「选择次数限制」判别背包子模型

拿到一道题，先回答三个问题：

仓库中 416. 分割等和子集（中等）(上).md.md) 将背包模型做了系统总结，而 322、518、279 三题则分别演示了完全背包在「求最少物品数」「求方案数」「求最少物品数」三个场景下的变形。下文将以这些仓库源码为实例，逐步展开。

二、题目索引：仓库「背包 DP」专题完整清单

以下是 LogicStack-LeetCode 仓库 Index/背包 DP.md 收录的全部背包类题目，难度与推荐指数沿用索引原文，题解列已转换为仓库内相对路径，便于直接查阅：

从「简单 → 中等 → 困难」的难度梯度可以看出，背包模型可以覆盖从入门到进阶的完整链路，而 416 上下两篇则专门用于精讲 01 背包从「间接求解」到「直接求解」的思维转换，是仓库中背包系列的核心篇章。

三、完全背包实战：322. 零钱兑换

3.1 题目与背包模型判别

给定不同面额的硬币coins和一个总金额amount，编写一个函数计算凑成总金额所需的最少硬币个数；若无任何硬币组合能组成总金额，返回-1。每种硬币数量无限。

约束：1 <= coins.length <= 12，1 <= coins[i] <= 2^31 - 1，0 <= amount <= 10^4。

硬币相当于物品，每种硬币可选择无限次，因此属于完全背包，目标是最小化「使用的硬币个数」。

3.2 状态定义与初始化

完全背包的原始状态定义是两维的：

• 第一维i代表物品编号（前 i 件物品）；
• 第二维j代表容量（背包容量 / 目标总和）。

定义f[i][j]为考虑前 i 件物品、凑成总和为 j 所需要的最少硬币数量。

初始化时引入「哨兵」思想：令f[0][x]代表「不考虑任何物品」的情况，于是：

• f[0][0] = 0：没有硬币时凑出总和 0，使用的硬币数为 0；
• 其余f[0][x] = INF：凑出其他总和的方案不存在。

由于求的是「最少」硬币数量，无效值不应参与转移，因此可设INF = INT_MAX（数学上的正无穷）。

3.3 朴素转移方程

对于第 i 个硬币（面值val），有两种决策：

• 不使用该硬币：f[i][j] = f[i-1][j]；
• 使用该硬币：由于每种硬币可被选择多次（容量允许的前提下），最优解为所有选择次数下的最小值：

f[i][j] = min( f[i-1][j-k*val] + k )，其中 1 <= k 且 k*val <= j

仓库中的朴素实现（见 322. 零钱兑换（中等）.md）：

class Solution { int INF = Integer.MAX_VALUE; public int coinChange(int[] cs, int cnt) { int n = cs.length; int[][] f = new int[n + 1][cnt + 1]; // 初始化：不考虑任何硬币时，只有 f[0][0] = 0，其余均为无效值 for (int i = 1; i <= cnt; i++) f[0][i] = INF; for (int i = 1; i <= n; i++) { int val = cs[i - 1]; for (int j = 0; j <= cnt; j++) { // 不考虑当前硬币 f[i][j] = f[i - 1][j]; // 考虑当前硬币（可选个数由当前容量决定） for (int k = 1; k * val <= j; k++) { if (f[i - 1][j - k * val] != INF) { f[i][j] = Math.min(f[i][j], f[i-1][j-k*val] + k); } } } } return f[n][cnt] == INF ? -1 : f[n][cnt]; } }

• 时间复杂度：共有n * cnt个状态需要转移，每个状态最多遍历cnt次，整体为O(n * cnt²)；
• 空间复杂度：O(n * cnt)。

3.4 深入：无效状态INF的定义艺术

这是仓库题解中一个非常有价值的工程细节。在「取最小值」的转移中，我们希望无效值（无法凑出的总和）不参与转移，因此INF应代表正无穷。但如果直接使用INT_MAX作为INF，一旦在其基础上累加（如f[i-1][j-k*val] + k），常规语言中整数会溢出变成负的最小值，丢失「正无穷」的语义——这与数学上正无穷可累加的概念相冲突。

因此朴素解法中出现了「先判断再使用」的模式：

if (f[i-1][j] != INF) { f[i][j] = Math.min(f[i][j], f[i-1][j]); }

每次使用都前置判断很麻烦，更优雅的工程技巧是：使用一个比INT_MAX小的较大数作为INF，为累加预留空间。例如0x3f3f3f3f（约 10.6 亿），它足够大以表示「正无穷」，又远小于INT_MAX（约 21.4 亿），即使累加若干次也不会溢出，从而省去所有前置判断：

class Solution { int INF = 0x3f3f3f3f; public int coinChange(int[] cs, int cnt) { int n = cs.length; int[][] f = new int[n + 1][cnt + 1]; for (int i = 1; i <= cnt; i++) f[0][i] = INF; for (int i = 1; i <= n; i++) { int val = cs[i - 1]; for (int j = 0; j <= cnt; j++) { f[i][j] = f[i-1][j]; for (int k = 0; k * val <= j; k++) { f[i][j] = Math.min(f[i][j], f[i-1][j-k*val] + k); } } } return f[n][cnt] == INF ? -1 : f[n][cnt]; } }

这个0x3f3f3f3f约定在仓库的 279、322 等多篇题解中一致使用，可以作为固定模板参数记忆。

3.5 完全背包的一维空间优化：站在「换元法」的高度

朴素的 O(n * cnt²) 在amount较大时会超时，需要做空间优化。仓库题解提供了一个比逐行数学推导更高效的理解角度——抽象「成本」与「价值」，结合换元法。

已知传统的完全背包二维转移方程：

f[i][j] = max( f[i-1][j], f[i-1][j-k*w[i]] + k*v[i] )

经过严格证明的一维优化形式（容量维度从小到大遍历）：

f[j] = max( f[j], f[j-w[i]] + v[i] )

回到本题，朴素状态转移方程为：

f[i][j] = min( f[i-1][j], f[i-1][j-k*coin] + k )

将硬币面值抽象为「成本」、硬币数量抽象为「价值」，消除物品维度，即得：

f[j] = min( f[j], f[j-coin] + 1 )

仓库中的一维优化实现：

class Solution { int INF = 0x3f3f3f3f; public int coinChange(int[] cs, int cnt) { int n = cs.length; int[] f = new int[cnt + 1]; for (int i = 1; i <= cnt; i++) f[i] = INF; for (int i = 1; i <= n; i++) { int val = cs[i - 1]; for (int j = val; j <= cnt; j++) { f[j] = Math.min(f[j], f[j - val] + 1); } } return f[cnt] == INF ? -1 : f[cnt]; } }

• 时间复杂度：O(n * cnt)；
• 空间复杂度：O(cnt)。

关键记忆点：完全背包的一维优化容量维度必须「从小到大」遍历（正序），因为每种物品可取无限次，正序遍历恰好允许同一物品在本轮被重复利用；而 01 背包的一维优化必须「从大到小」遍历（倒序），以保证每件物品至多被取一次。这一正一反的对比，在下文的 416 题中会再次出现。

3.6 同模型延伸：279. 完全平方数

279. 完全平方数（中等）.md 是同一模型的最小改动版本：预处理出所有不超过 n 的完全平方数[1, 4, 9, ...]作为「物品」，每个数字可使用无限次，求凑出 n 所需的最少数字个数。状态定义、初始化（f[0][0]=0、其余INF）与转移方程与 322 完全一致，只是物品集合由「硬币面额」换成了「完全平方数」，可视为对 322 模板的「换汤不换药」验证。

四、01 背包实战：416. 分割等和子集（上下两篇）

4.1 题目与模型判别

给你一个只包含正整数的非空数组nums，判断是否可以将数组分割成两个子集，使得两个子集的元素和相等。

约束：1 <= nums.length <= 200，1 <= nums[i] <= 100。

要分成两个元素和相等的子集，等价于能否选出若干元素，使其总和恰好为数组总和的一半（记target = sum / 2）。每个元素至多选一次，属于01 背包；且只问「能否」，属于「恰好型」布尔判定问题。

4.2 上篇：将「间接求解」转为「直接求解」

仓库题解（上）416. 分割等和子集（中等）(上).md.md) 讲的是 01 背包的基础推导：先以「总和不超过 j 的最大价值」这种经典间接状态入手，再论证如何调整。

题解（下）416. 分割等和子集（中等）(下).md.md) 则完成了关键的一步——修改状态定义，使其与答案直接相关：

• 原定义：f[i][j]代表考虑前 i 个数值、选择总和不超过 j 的最大价值；
• 新定义：f[i][j]代表考虑前 i 个数值、选择总和是否恰好为 j（布尔类型）。

对应转移方程（∨为逻辑或）：

f[i][j] = f[i-1][j] ∨ f[i-1][j-nums[i]]

含义：想要「考虑前 i 个数值且总和恰好为 j」为真，需要下列两种方案至少一种为真：

1. 不选第 i 件物品：f[i-1][j]为 true；
2. 选第 i 件物品：f[i-1][j-nums[i]]为 true。

4.3 修改状态定义后的「初始化」陷阱

仓库题解特别强调：修改了状态定义之后，除了调整转移方程，还必须重新设计初始化。布尔数组初始值全为 false，若不注入有效值，递推将永远无法产生 true。

通常使用「首行」来初始化有效值，并配合「哨兵」思想：将物品编号从 0 调整为从 1 开始，让f[0][x]代表「不考虑任何物品」的情况，于是f[0][0] = true作为唯一有效起点，完美规避了「第一个物品过大、永远装不进背包」的边界问题。

完整常规解法（见题解下篇）：

class Solution { public boolean canPartition(int[] nums) { int n = nums.length; //「等和子集」的和必然是总和的一半 int sum = 0; for (int i : nums) sum += i; int target = sum / 2; // 总和为奇数时，注定无法分为两个等和子集 if (target * 2 != sum) return false; // f[i][j] 代表考虑前 i 件物品，能否凑出价值「恰好」为 j 的方案 boolean[][] f = new boolean[n+1][target+1]; f[0][0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = 0; j <= target; j++) { // 不选该物品 boolean no = f[i-1][j]; // 选该物品 boolean yes = j >= t ? f[i-1][j-t] : false; f[i][j] = no | yes; } } return f[n][target]; } }

• 时间复杂度：O(n * target)；
• 空间复杂度：O(n * target)。

4.4 滚动数组优化：压缩物品维度

滚动数组将物品维度压缩为 2，用i & 1在两层之间交替，空间复杂度降为O(target)：

class Solution { public boolean canPartition(int[] nums) { int n = nums.length; int sum = 0; for (int i : nums) sum += i; int target = sum / 2; if (target * 2 != sum) return false; // 修改「物品维度」为 2 boolean[][] f = new boolean[2][target+1]; f[0][0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = 0; j <= target; j++) { boolean no = f[(i-1)&1][j]; boolean yes = j >= t ? f[(i-1)&1][j-t] : false; f[i&1][j] = no | yes; } } return f[n&1][target]; } }

4.5 一维空间优化：01 背包必须「从大到小」遍历

与完全背包正序相反，01 背包的一维优化必须倒序遍历容量，以保证每件物品至多被取一次（正序会导致同一物品被重复选取，退化为完全背包）：

class Solution { public boolean canPartition(int[] nums) { int n = nums.length; int sum = 0; for (int i : nums) sum += i; int target = sum / 2; if (target * 2 != sum) return false; // 取消「物品维度」 boolean[] f = new boolean[target+1]; f[0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = target; j >= 0; j--) { boolean no = f[j]; boolean yes = j >= t ? f[j-t] : false; f[j] = no | yes; } } return f[target]; } }

4.6 进阶变形：1049. 最后一块石头的重量 II

1049. 最后一块石头的重量 II（中等）.md 是 416 的隐藏变体：每次选两块石头相撞，等价于给每块石头赋予正负号，问题转化为「将石头分成两组，求两组总和之差的最小值」，即 01 背包求「不超过 sum/2 的最大可达值」。理解了 416 的「恰好型」状态，就能自然迁移到「不超过型」状态，属于对同一模型的二次应用。

五、一题多解示范：494. 目标和

给定非负整数数组nums和目标整数target，向每个整数前添加+或-，求可以凑成目标和的表达式数目。

仓库题解 494. 目标和（中等）.md 提供了完整的「一题四解」路线：DFS → 记忆化搜索 → 01 背包，展示了同一问题在不同算法视角下的演进。

5.1 解法一：DFS 爆搜

数据范围只有 20，每个数只有+/-两种选择，可直接 DFS：

class Solution { public int findTargetSumWays(int[] nums, int t) { return dfs(nums, t, 0, 0); } int dfs(int[] nums, int t, int u, int cur) { if (u == nums.length) { return cur == t ? 1 : 0; } int left = dfs(nums, t, u + 1, cur + nums[u]); int right = dfs(nums, t, u + 1, cur - nums[u]); return left + right; } }

• 时间复杂度：O(2^n)。

5.2 解法二：记忆化搜索

DFS 的可变参数只有「下标 u」和「当前结果 cur」，可作记忆化容器的两个维度；由于cur可能为负，仓库实现选用哈希表存储：

class Solution { public int findTargetSumWays(int[] nums, int t) { return dfs(nums, t, 0, 0); } Map<String, Integer> cache = new HashMap<>(); int dfs(int[] nums, int t, int u, int cur) { String key = u + "_" + cur; if (cache.containsKey(key)) return cache.get(key); if (u == nums.length) { cache.put(key, cur == t ? 1 : 0); return cache.get(key); } int left = dfs(nums, t, u + 1, cur + nums[u]); int right = dfs(nums, t, u + 1, cur - nums[u]); cache.put(key, left + right); return cache.get(key); } }

• 时间复杂度：O(n * Σ|nums[i]|)。

5.3 解法三：转化为 01 背包

记忆化搜索的本质已经接近动态规划。令sum = Σnums[i]，设取+的元素和为p，则取-的元素和为sum - p，目标target = p - (sum - p)，解得p = (sum + target) / 2（需满足sum + target为偶数且不小于 0）。于是问题转化为：从数组中选出若干元素、使其和恰好为 p 的方案数——标准的 01 背包「恰好型方案数」问题，初始化f[0] = 1、其余为 0。这再次印证了「识别背包模型」的核心能力：先把题目改写为背包的标准形式，再套用模板。

六、完全背包求方案数：518. 零钱兑换 II

给定不同面额的硬币和一个总金额，计算可以凑成总金额的硬币组合数，每种硬币数量无限。

仓库题解 518. 零钱兑换 II（中等）.md 指出：322 求「最少物品个数」，本题求「凑出特定价值的方案数量」，求的东西不同，但问题本质没有变，同样属于组合优化问题。

状态定义微调为：f[i][j]为考虑前 i 件物品、凑成总和为 j 的方案数量。初始化f[0][0] = 1（不选任何硬币凑出 0，方案数为 1），其余f[0][x] = 0。

朴素转移（k 表示选 k 个第 i 种硬币）：

f[i][j] = f[i-1][j] + Σ f[i-1][j-k*val]，其中 1 <= k <= ⌊j/val⌋

朴素实现：

class Solution { public int change(int cnt, int[] cs) { int n = cs.length; int[][] f = new int[n + 1][cnt + 1]; f[0][0] = 1; for (int i = 1; i <= n; i++) { int val = cs[i - 1]; for (int j = 0; j <= cnt; j++) { f[i][j] = f[i - 1][j]; for (int k = 1; k * val <= j; k++) { f[i][j] += f[i - 1][j - k * val]; } } } return f[n][cnt]; } }

同样可套用完全背包一维优化（容量正序遍历），得到f[j] = f[j] + f[j-val]的简洁形式。注意：这里求的是「组合数」，若求「排列数」（如爬楼梯类问题）则需调整遍历顺序，题解中对此有细致区分。

七、多维背包与分组背包进阶

7.1 多维背包：474. 一和零

474. 一和零（中等）.md 中每个字符串（物品）同时消耗「0 的个数」与「1 的个数」两个资源，因此状态从一维容量扩展为二维：f[i][j][k]代表考虑前 i 个字符串、消耗不超过 j 个 0 和 k 个 1 时能选取的最大字符串数量。这展示了背包容量维度可以不止一个，转移时只需对每个资源维度分别做 01 背包的容量判断与倒序更新即可。

7.2 分组背包与多维约束：879. 盈利计划、1155. 掷骰子

879. 盈利计划（困难）.md 是「特殊多维背包」：每项工作消耗成员数并产生利润，需同时满足「成员不超过 n」与「利润不少于 minProfit」两个约束，属于带双向约束的 01 背包变形，难度为困难。

880. 掷骰子的N种方法（中等）.md 则可抽象为分组背包：n 个骰子等价于 n 组，每组（每个骰子）必须且只能选一个点数（1~f），求各点数之和恰好为 target 的方案数。仓库中另有同题副本文件，内容一致，可对照阅读。

7.3 背包思想的延伸应用

背包模型的边界非常宽泛，仓库中还有大量「披着其他外衣」的背包题：

• 1449. 数位成本和为目标值的最大数字（困难）：数字 0~9 各有成本，求成本总和恰好为 target 时能拼出的最大数字，是「恰好型完全背包 + 字典序贪心」的结合，见 题解；
• 1995. 统计特殊四元组（简单）：虽然是简单题，但题解给出了「枚举 + 哈希」「DP」等多条路径，其中 DP 视角可视为对「子集和」思想的轻量应用，见 题解；
• 638. 大礼包（中等）：混合了「完全背包」与「状态压缩」思想，仓库 LeetCode/631-640/ 目录下有完整题解。

八、背包 DP 解题模板与速查表

综合仓库多篇题解，可沉淀出如下可复用的解题流程：

8.1 四步解题流水线

1. 判别模型：物品选择次数（至多一次 → 01；无限次 → 完全；每组至多一个 → 分组）+ 容量维度个数（多维背包）；
2. 设计状态：f[i][j]第一维为物品编号，第二维为容量；明确是「不超过 j」「恰好为 j」还是「至少为 j」，这决定了初始化与最终答案的取法；
3. 推导转移：对每个物品写出「不选」与「选 k 个」的候选，取最值或求和；
4. 空间优化：先滚动数组，再一维化；01 背包容量倒序，完全背包容量正序。

8.2 关键参数与边界速查

九、如何在仓库中系统学习与验证

LogicStack-LeetCode 仓库以「日更题解」方式沉淀了完整的刷题系列（见 README.md），背包 DP 专题可从以下入口进入：

1. 索引入口：先读 Index/背包 DP.md，按推荐指数（🤩 数量）规划学习顺序，从 4 星基础题入手，再挑战 5 星进阶题；
2. 成对阅读：416 题分上、下两篇，务必按顺序阅读——上篇讲「间接求解」与 01 背包基础，下篇讲「直接求解」的状态重构与三种空间优化，是理解「修改状态定义必须同步修改初始化」这一核心思想的最佳素材；
3. 代码验证：每篇题解的 Java 代码均可直接复制到 LeetCode 提交验证；关注INF = 0x3f3f3f3f、滚动数组i & 1、容量正序/倒序这三个「模板关键点」，对照本文速查表逐一确认；
4. 举一反三：用 322（求最少）与 518（求方案数）对照理解「同一模型、不同目标」；用 416 与 494 对照理解「布尔判定」与「方案计数」的状态差异。

背包问题的价值不在于背模板，而在于建立「识别组合优化 → 匹配背包模型」的思维反射。当你看到「给定若干物品，选择以达到某目标」时，脑海中应自动弹出这套框架——这也是仓库中 322、416、518 等多篇题解反复强调的核心能力。将本文速查表与仓库题解结合使用，即可系统性掌握从 01 背包到多维背包的完整知识体系。

• 教程
• 文档