完全背包遍历顺序与组合/排列的关系

完全背包遍历顺序与组合/排列的关系原理解读 · 算法进阶主题标签组合 · 排列 · 正序 · 倒序 · 完全背包 · 0-1背包Slide 1概论主标题完全背包副标题遍历顺序与组合/排列的关系关键词标签组合、排列、正序、倒序、完全背包、0-1背包Slide 2先理清概念——组合 vs 排列组合Combination—— 与顺序无关从 N 个不同元素中取出 K 个不考虑取出顺序。相同的元素集合只算一种结果。示例coins [1, 2]凑成 3{1, 2}1种组合先取1后取2 ≠ 先2后1不分开计算排列Permutation—— 与顺序有关从 N 个不同元素中取出 K 个考虑取出顺序。相同元素不同顺序算不同结果。示例coins [1, 2]凑成 3[1, 2]和[2, 1]2种排列顺序不同则是不同的选取序列Slide 3完全背包的两种遍历顺序问题背景每个物品可选无限次最终能凑成的方案数问组合还是排列顺序 A物品外层容量内层正序→ 组合intways0;vectorintdp(W1,0);dp[0]1;// 物品外层for(inti0;iN;i){// 容量正序for(intjw[i];jW;j){dp[j]dp[j-w[i]];}}waysdp[W];顺序 B容量外层物品内层 → 排列intways0;vectorintdp(W1,0);dp[0]1;// 容量外层for(intj1;jW;j){// 物品内层for(inti0;iN;i){if(jw[i])dp[j]dp[j-w[i]];}}waysdp[W]; 两段代码只有两层循环的顺序不同正是这个顺序差异产生了组合与排列的区别关键区别顺序 A物品维度在外层每个物品 i 被完整处理后才处理下一个物品 →物品顺序固定→ 组合顺序 B容量维度在外层每个容量 j 会遍历所有物品 i → 相同容量的不同物品选取顺序都被计入 →排列Slide 4核心原理核心原则「先处理的维度」决定了计数的顺序含义外层循环的维度 被固定的维度 不参与排列的维度物品外层 → 组合外层循环遍历物品 i 物品顺序被固定当处理物品 i 时前 i-1 个物品已被完全处理不同物品之间的选取顺序被固化对于容量 j每个物品 i 只被考虑一次在本次遍历中结果相同元素集合只计一次与选取顺序无关容量外层 → 排列外层循环遍历容量 j 容量顺序被固定在同一个容量 j 下所有物品 i 都会被尝试选取先选物品 A 还是先选物品 B会在不同迭代路径中被计入dp[j]累积了以任意物品序列到达 j 的所有路径结果相同元素集合不同顺序计多次与选取顺序有关Slide 5过程图解——coins [1, 2]target 3顺序 A物品外层→ 组合 1种步骤dp 状态初始[1, 0, 0, 0]i0 (coin1)[1, 1, 2, 3]i1 (coin2)[1, 1, 2, 3]j3: max(3, dp[1]23)含义dp[3] 3 → 选取{1,1,1}或{1,2}{1,2}和{2,1}被视为同一组合顺序 B容量外层→ 排列 2种步骤dp 状态初始[1, 0, 0, 0]j1[1, 1, 0, 0]// dp[1] dp[0] (coin1)j2[1, 1, 2, 0]// dp[2] dp1 dp0j3[1, 1, 2, 3]// dp[3] dp2 dp1 → 3种含义dp[3] 3 →{1,1,1}、{1,2}、{2,1}{1,2}和{2,1}被计为不同排列⚠️注意虽然 dp[3] 的数值相同都是 3但数值 3 的含义完全不同顺序A3种组合方案{1,1,1}、{1,2}顺序B3种排列序列{1,1,1}、{1,2}、{2,1}Slide 6更复杂示例——coins [1, 2, 5]target 5顺序 A物品外层→ 组合4种组合说明{5}1个5{2,2,1}221{2,1,1,1}2111{1,1,1,1,1}全1顺序 B容量外层→ 排列13种排列说明[5]1个5[2,2,1]/[2,1,2]/[1,2,2]3种排列[2,1,1,1]/[1,2,1,1]/ …4种排列[1,1,1,1,1]1种dp 值对比dp[1]dp[2]dp[3]dp[4]dp[5]顺序A组合11224顺序B排列123513Slide 7为什么最大价值时结果相同核心结论对于「最大价值」问题组合与排列的结果一定相同因为「最大价值」只关心「能否达到」不关心「以多少种方式达到」。两种遍历顺序都会选最有价值的物品组合结果相同。三种场景对比场景 1求最大价值时结论顺序 A 顺序 B原因max操作有幂等性max(..., max(...)) max(...)状态转移dp[j] max(dp[j], dp[j-w[i]] v[i])场景 2求方案数时组合—— 顺序 A 正确原因外层物品固定了选取顺序同一物品集合只计一次{1,2}和{2,1}是同一组合状态转移dp[j] dp[j-w[i]] // 正序场景 3求方案数时排列—— 顺序 B 正确原因外层容量遍历所有物品不同选取顺序被分别计入{1,2}和{2,1}是不同排列状态转移dp[j] dp[j-w[i]] // 针对每个物品Slide 8LeetCode 典型例题对应LeetCode 518 —— 零钱兑换 II类型组合顺序 A问题给定硬币种类无限枚求凑成金额的组合数代码for(intcoin:coins)for(intjcoin;jamount;j)dp[j]dp[j-coin];原理外层 coin → 硬币顺序固定 → 每种硬币被处理一次不同硬币选取顺序固定 →{1,2}和{2,1}计为同一组合LeetCode 377 —— 组合总和 IV类型排列顺序 B问题给定正整数数组求凑成目标和的排列数顺序敏感代码for(intj1;jtarget;j)for(intnum:nums)if(jnum)dp[j]dp[j-num];原理外层 j → 金额逐个计算 → 每个金额会遍历所有数字不同选取顺序分别计入 →{1,2}和{2,1}是不同排列Slide 9通用规律总结规则 01外层维度固定被计数维度外层循环是物品→ 物品顺序被固定 →组合外层循环是容量→ 容量顺序被固定 → 每种选取路径分别计数 →排列规则 02max 求最优值时两种顺序等价用max做状态转移时无论哪种顺序最终都收敛到同一个最大值因为最优解不关心路径数量。规则 03 求方案数时顺序决定含义用做状态转移时外层是物品 →组合数外层是容量 →排列数这是最常考的理解性考点规则 04一维完全背包内层必须正序完全背包的一维实现中内层容量必须正序遍历使得dp[j-w[i]]是本轮 i 的已更新值允许同物品多次选取。规则 050-1 背包与完全背包的遍历区别类型内层循环方向原因0-1 背包倒序保护上一行每个物品只选一次完全背包正序利用本行更新允许同物品多次选取组合问题物品外层物品顺序固定 → 组合排列问题容量外层容量顺序固定 → 排列掌握这5条通用规律所有背包变种中的遍历顺序问题都能系统化解决