企业官网建设流程全解析

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

原理解读 · 算法进阶

主题标签：组合 · 排列 · 正序 · 倒序 · 完全背包 · 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：物品外层，容量内层（正序）→ 组合

intways=0;vector<int>dp(W+1,0);dp[0]=1;// 物品外层for(inti=0;i<N;i++){// 容量正序for(intj=w[i];j<=W;j++){dp[j]+=dp[j-w[i]];}}ways=dp[W];

顺序 B：容量外层，物品内层 → 排列

intways=0;vector<int>dp(W+1,0);dp[0]=1;// 容量外层for(intj=1;j<=W;j++){// 物品内层for(inti=0;i<N;i++){if(j>=w[i])dp[j]+=dp[j-w[i]];}}ways=dp[W];

💡 两段代码只有两层循环的顺序不同，正是这个顺序差异产生了组合与排列的区别

关键区别：

• 顺序 A（物品维度在外层）：每个物品 i 被完整处理后，才处理下一个物品 →物品顺序固定→ 组合
• 顺序 B（容量维度在外层）：每个容量 j 会遍历所有物品 i → 相同容量的不同物品选取顺序都被计入 →排列

Slide 4：核心原理

核心原则

「先处理的维度」决定了计数的顺序含义

外层循环的维度 = 被固定的维度 = 不参与排列的维度

物品外层 → 组合

1. 外层循环遍历物品 i =物品顺序被固定
2. 当处理物品 i 时，前 i-1 个物品已被完全处理
3. 不同物品之间的选取顺序被固化
4. 对于容量 j，每个物品 i 只被考虑一次（在本次遍历中）
5. 结果：相同元素集合只计一次，与选取顺序无关

容量外层 → 排列

1. 外层循环遍历容量 j =容量顺序被固定
2. 在同一个容量 j 下，所有物品 i 都会被尝试选取
3. 先选物品 A 还是先选物品 B，会在不同迭代路径中被计入
4. dp[j]累积了以任意物品序列到达 j 的所有路径
5. 结果：相同元素集合不同顺序计多次，与选取顺序有关

Slide 5：过程图解——coins = [1, 2]，target = 3

顺序 A（物品外层）→ 组合 = 1种

含义：dp[3] = 3 → 选取{1,1,1}或{1,2}

{1,2}和{2,1}被视为同一组合

顺序 B（容量外层）→ 排列 = 2种

含义：dp[3] = 3 →{1,1,1}、{1,2}、{2,1}

{1,2}和{2,1}被计为不同排列

⚠️注意：虽然 dp[3] 的数值相同（都是 3），但数值 3 的含义完全不同！

• 顺序A：3种组合方案（{1,1,1}、{1,2}）
• 顺序B：3种排列序列（{1,1,1}、{1,2}、{2,1}）

Slide 6：更复杂示例——coins = [1, 2, 5]，target = 5

顺序 A（物品外层）→ 组合：4种

顺序 B（容量外层）→ 排列：13种

dp 值对比

Slide 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 8：LeetCode 典型例题对应

LeetCode 518 —— 零钱兑换 II

类型：组合（顺序 A）

问题：给定硬币种类（无限枚），求凑成金额的组合数

代码：

for(intcoin:coins)for(intj=coin;j<=amount;j++)dp[j]+=dp[j-coin];

原理：外层 coin → 硬币顺序固定 → 每种硬币被处理一次，不同硬币选取顺序固定 →{1,2}和{2,1}计为同一组合

LeetCode 377 —— 组合总和 IV

类型：排列（顺序 B）

问题：给定正整数数组，求凑成目标和的排列数（顺序敏感）

代码：

for(intj=1;j<=target;j++)for(intnum:nums)if(j>=num)dp[j]+=dp[j-num];

原理：外层 j → 金额逐个计算 → 每个金额会遍历所有数字，不同选取顺序分别计入 →{1,2}和{2,1}是不同排列

Slide 9：通用规律总结

规则 01：外层维度固定被计数维度

• 外层循环是物品→ 物品顺序被固定 →组合
• 外层循环是容量→ 容量顺序被固定 → 每种选取路径分别计数 →排列

规则 02：max 求最优值时两种顺序等价

用max做状态转移时，无论哪种顺序，最终都收敛到同一个最大值，因为最优解不关心路径数量。

规则 03：+= 求方案数时顺序决定含义

用+=做状态转移时：

• 外层是物品 →组合数
• 外层是容量 →排列数

这是最常考的理解性考点

规则 04：一维完全背包内层必须正序

完全背包的一维实现中，内层容量必须正序遍历，使得dp[j-w[i]]是本轮 i 的已更新值（允许同物品多次选取）。

规则 05：0-1 背包与完全背包的遍历区别

掌握这5条通用规律，所有背包变种中的遍历顺序问题都能系统化解决