1. 先确认三个条件
先读动态规划主文。背包题必须确认:每件物品可用几次?容量是不超过还是恰好?求最大价值、最少数量还是方案数?这三点决定初始化和转移,不是只背循环方向。
以下输入按题目保证:容量/金额为非负整数,重量/面额为正整数,价值为非负安全整数,所有中间值和答案仍安全;数组规模可分配。不修改输入。
2. 零一背包:每件最多一次
定义二维状态 dp[i][v] 为前 i 件物品、总重量不超过 v 的最大价值。选择当前物品时依赖上一行的 dp[i - 1][v - weight],不选时依赖 dp[i - 1][v]。没有物品时价值为零,所以全部初始化为零。
压成一维后必须倒序更新容量,使被读取的小容量仍来自上一阶段;正序会重复使用当前物品。
function knapsack01(weights, values, capacity) {
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let v = capacity; v >= weights[i]; v--) {
dp[v] = Math.max(dp[v], dp[v - weights[i]] + values[i]);
}
}
return dp[capacity];
}要求重量与价值数组等长。weights = [2]、values = [3]、容量 4 时只能得到 3,不是 6。时间为 O(nV),辅助空间为 O(V),容量值本身参与复杂度,因此是伪多项式算法。
若要求恰好装满,应只有 dp[0] = 0,其余初始化为负无穷;不可达状态不能被当成零价值。最后仍不可达就按题目约定返回无解。本实现明确求“不超过”,不支持直接混用。
3. 完全背包:零钱最少数量
每种硬币无限个,因此零钱兑换属于完全背包,不属于零一背包。定义 dp[a] 为恰好组成金额 a 的最少枚数,dp[0] = 0,其他金额初始不可达。
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}依赖金额更小的状态,因此金额正序。空硬币数组只能组成零;无法组成目标返回 -1。时间为 O(kA),辅助空间为 O(A)。[1,3,4] 组成 6 的答案为 2,也说明优先拿大面额的贪心不总正确。
4. 方案计数:组合不能重复算顺序
定义 dp[a] 为只使用已处理面额组成金额 a 的组合数。面额必须互不重复;同一组合不区分硬币排列顺序。
function coinCombinations(coins, amount) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
for (let a = coin; a <= amount; a++) {
dp[a] += dp[a - coin];
}
}
return dp[amount];
}面额在外层避免把同一组合按不同顺序计数,金额正序允许当前面额重复使用。[1,2] 组成 3 有 2 种组合,而按顺序计数是 3 种。空方案使零金额答案为 1。时间为 O(kA),辅助空间为 O(A)。
原来的固定面额 [1,5,10,25] 硬币题可以使用本模型。若题目要求模 1000000007,每次相加后取模,且确认中间加法在精确整数范围内;本函数保留精确计数,只适用于答案安全的规模。
5. 进阶分类保留为选学地图
| 变式 | 增加的约束 | 学习任务 |
|---|---|---|
| 多重/混合背包 | 使用次数有限或各不相同 | 将可选次数明确写入转移,先用小输入枚举核对 |
| 二维费用 | 同时限制两个资源 | 状态增加一个容量维度,检查两个方向 |
| 分组背包 | 每组最多选一件 | 用上一组的状态转移,避免同组重复选 |
| 方案恢复/方案数 | 不只要最优值 | 分别记录选择来源或计数;平局时按契约处理 |
| 依赖背包 | 选子项前必须选父项 | 先画依赖树,再研究子树状态合并 |
这些是常见变式,不是“背包总共只有九种”的固定分类。第一轮完成前三个模型即可。
6. 验证与练习
运行 node --test tests/algorithm-strategies-examples.test.mjs。验证零容量、空物品、放不下、重复重量、无法凑成和组合顺序。闭卷解释:为什么零一背包倒序,而完全背包允许正序?用一件重量为 2 的物品手推到容量 4。
评论
正在加载评论…