企业官网建设流程全解析

背包问题是动态规划里最典型的入门题，也是很多C#开发者从暴力搜索转向动态规划的第一道坎。面试时如果有人突然问“0-1背包怎么写”，你心里必须立刻浮出状态转移方程，而不是现场枚举所有子集。这篇文章我打算用一种自己一直在用的拆解方式，把C#解决背包问题的完整路径讲透：从暴力搜索为什么不行、到动态规划原理、再到四种常见变体的代码实现和避坑记录。适合准备算法面试的.NET开发者，也适合工作多年突然要补算法课的同行。

1. 为什么暴力搜索在背包问题上走不远

1.1 背包问题的三种经典形态

先把题目说清楚。日常大家说的“背包问题”，最常遇到的是三种基本形态。

0-1背包是说有n个物品，每个物品要么拿、要么不拿，只能做一次选择，每个物品都有自己的重量w[i]和价值v[i]，背包容量是W，目标是在不超重的前提下让装入物品的总价值最大。这是最基础的版本，也是后面所有变体的根基。

完全背包改了一个条件：每个物品可以拿无限次。也就是说同样的物品你可以反复往包里塞，只要总重量不超就行。它和0-1背包看起来只差一点点，但解法里内层循环方向要反过来，这是很多新手第一次踩坑的地方。

多重背包介于两者之间：第i种物品最多只能拿c[i]个。它可以被看成是0-1背包的特殊情况，但如果直接按数量展开，物品数量会变得很大，需要用二进制拆分做优化。

除了这三种，还有分组背包、依赖背包、混合背包等变体。但不管怎么变，核心都是用动态规划的状态和转移去覆盖所有选择。先理解这三种，后面的变体都能顺下来。

1.2 暴力搜索的时间复杂度到底有多恐怖

很多人一开始会写递归枚举，思路很简单：从第0个物品开始，对每个物品做两个分支——拿或者不拿，最后在所有合法组合里找一个最大价值。代码写起来确实短：

public int BruteForce(int i, int restCapacity, int[] w, int[] v) { if (i == w.Length || restCapacity <= 0) return 0; // 不拿当前物品 int skip = BruteForce(i + 1, restCapacity, w, v); // 拿当前物品（前提是放得下） int take = restCapacity >= w[i] ? BruteForce(i + 1, restCapacity - w[i], w, v) + v[i] : 0; return Math.Max(skip, take); }

这个写法逻辑非常直白，但它的问题在于分支数量是2^n。n等于30的时候，总调用次数已经超过10亿，就算每个分支只做一次简单的加法和比较，在单机上也得好几秒；n到40的时候是1万亿次调用，彻底跑不动。

我之前见过有人拿这个递归去跑面试题，物品数量只有25个，测试用例看起来不大，但实际跑起来花了将近一分钟，就是因为没有加记忆化。暴力搜索最致命的地方在于：它完全没有复用中间结果。前一个物品选和不选，两个分支后面还要继续展开，后面的子问题被重复计算了无数次。

有人会说，那我加个剪枝不就行了？比如当前剩余容量装不下任何物品就停。可剪枝只能缓解一部分情况，遇到每个物品都很小、容量又大的数据，照样爆炸。背包问题本质上是在一堆组合里做优化选择，暴力枚举把“所有组合”都列出来，而动态规划只枚举“所有状态”，这才是差距的根源。

2. 动态规划的核心思路：状态、转移与填表

2.1 状态定义：dp[i][j]到底在表达什么

动态规划的第一步不是写代码，而是定义状态。对背包问题来说，最经典的状态定义是：

dp[i][j]表示“只考虑前i个物品，背包容量恰好为j（或者不超过j）时，能获得的最大价值”。

这里有一个很多人没想清楚的点：i不表示“已经拿了i个物品”，而是“前面的第0到第i-1个物品都已经做完了决策”。这样定义之后，整个问题的答案就是dp[n][W]，也就是“所有n个物品都考虑完，容量限制为W时能取到的最大价值”。

为什么要这么定义？因为它天然是一个递推结构。你想知道前i个物品的最优解，可以从前i-1个物品的最优解推导过来——要么不拿第i个物品，要么拿第i个物品。这两种情况分别对应：

• 不拿：dp[i][j] = dp[i-1][j]
• 拿：如果j >= w[i-1]，那么dp[i][j] = dp[i-1][j - w[i-1]] + v[i-1]

注意我们的物品下标从0开始，所以第i个物品在数组里的下标是i-1。这是写代码时最容易错的地方之一。

状态定义定了，整个问题就可以看作是在一个(n+1) × (W+1)的表格里逐格填充。每一格的值只依赖上一行同一列和上一行左侧的某个位置，天然适合循环处理。

2.2 状态转移方程是怎么来的

状态转移方程是整个动态规划的灵魂，背包问题的转移方程其实就是一个最大值决策：

dp[i][j] = max( dp[i-1][j], j >= w[i-1] ? dp[i-1][j - w[i-1]] + v[i-1] : 0 )

这个方程不需要背，你需要理解的是“为什么只比较这两种情况”。因为第i个物品的决策只有两种：拿或者不拿。不拿，那么前i个物品的最优解就等于前i-1个物品在同样容量下的最优解；拿，那么你得先腾出w[i-1]的空间，用剩余容量j - w[i-1]去装前i-1个物品，最后加上第i个物品的价值。

关键在于，一旦dp[i-1][x]这个值被算出来了，它就再也不会变，而且它已经代表了前i-1个物品在所有不超过容量x的情况下的最优选择。这样后面的计算就不需要重新去枚举前面的组合，直接拿之前算好的结果用就行。这就是动态规划所谓“最优子结构”的含义。

有些教材会把状态写成“容量不超过j”，有些写成“容量恰好为j”，两者有细微差别。对于“不超过”的写法，初始化要全部填0；对于“恰好”的写法，初始化时需要把dp[0][j](j > 0)设为负无穷，表示“用0个物品恰好填满容量j是不可能的”。后面第6章我会专门说这个坑。

2.3 为什么填表能碾压递归穷举

递归穷举慢，是因为同一个子问题会被反复算。动态规划慢下来没有？它把每个dp[i][j]只算一遍，总共n × W个格子，所以时间复杂度是O(n × W)。

举个例子，假设n = 1000，W = 1000，暴力枚举是2^1000，直接在宇宙热寂之前都跑不完；而动态规划只需要算1000 × 1000 = 100万个状态，在C#里就是几个毫秒的事。这个差距不是“优化了一点”，而是从“完全不可行”变成了“秒出结果”。

但这里要澄清一个概念：O(n × W)里的W是背包容量的数值，不是输入元素的个数，所以严格来说它叫“伪多项式时间”。如果W非常大，比如到了10^9，这个算法照样开不了数组、跑不动循环。这种时候有别的技巧，比如把容量和价值互换，用dp[v]表示“达到价值v所需的最小容量”，按价值维度去递推。不过那是进阶话题，绝大多数面试和工程场景下，W范围是可控的，O(n × W)完全够用。

记忆化搜索和填表DP本质上是同一个东西，只是方向不同：记忆化是自顶向下的递归，加上memo数组避免重复计算；填表是自底向上的迭代。如果你只想快速实现一个解法，记忆化更贴近人的直觉：

private int[,] _memo; public int DfsMemo(int i, int rest, int[] w, int[] v) { if (i == w.Length || rest <= 0) return 0; if (_memo[i, rest] != -1) return _memo[i, rest]; int skip = DfsMemo(i + 1, rest, w, v); int take = rest >= w[i] ? DfsMemo(i + 1, rest - w[i], w, v) + v[i] : 0; return _memo[i, rest] = Math.Max(skip, take); }

记忆化的时间复杂度和填表一样，都是O(n × W)，但递归调用本身有栈开销。所以工程上我更推荐迭代填表，性能更稳定，后面这几种代码也都能直接复用。

3. C#实现0-1背包：从二维DP到滚动数组

3.1 最直观的二维DP写法

直接给代码，这是最标准的0-1背包实现，先在二维表里把每种“前i个物品、容量j”的情况算出来，最后取右下角：

public int Knapsack01(int[] weights, int[] values, int capacity) { int n = weights.Length; int[,] dp = new int[n + 1, capacity + 1]; for (int i = 1; i <= n; i++) { int w = weights[i - 1]; int v = values[i - 1]; for (int j = 0; j <= capacity; j++) { if (j >= w) dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - w] + v); else dp[i, j] = dp[i - 1, j]; } } return dp[n, capacity]; }

几个值得说的细节：

第一，dp数组的行数是n + 1，不是n，因为第0行代表“一个物品都不考虑”的边界状态，全部是0。如果数组开成n，边界处理会非常别扭。

第二，外层循环从1到n，依次把每个物品嵌入决策；内层循环遍历所有可能的容量。每次用到dp[i-1]行，所以逻辑上每一行的计算只依赖上一行。

第三，用Math.Max取“不拿”和“拿”中的较大者。有人会问，为什么不拿和拿两者取一个最大就够了？因为在容量j固定的情况下，你确实只能在这两个动作里选一个。这个问题没有第三个选择：不可能“既拿又不拿”，也不可能“拿半个”。

空间上，(n + 1) × (W + 1)的int数组，在n = 2000、W = 2000时大约是2001 × 2001 × 4字节，约16MB，还能接受。但到了n = 10000、W = 100000，直接需要4GB以上内存，这时候基本上就爆了。所以必须降维。

3.2 滚动数组降维：把空间复杂度打到O(W)

观察上一节可以发现，dp[i][j]永远只依赖dp[i-1][...]，和dp[i-2]、dp[i-3]完全无关。也就是说，整张二维表里真正有价值的只有“上一行”的数据，更早的行都可以丢掉。

于是我们可以把dp压成一维数组：dp[j]表示“当前已经处理完前i-1个物品后，容量为j时的最大价值”。每处理一个物品，就在原地更新这个数组。关键的问题是更新顺序，如果内层循环还是从0到capacity正序走，就会把本轮刚刚更新过的dp[j-w]再拿去计算，导致同一个物品被使用多次，那0-1背包就变质了。

正确写法是内层从capacity倒着走到w：

public int Knapsack01Optimized(int[] weights, int[] values, int capacity) { int[] dp = new int[capacity + 1]; for (int i = 0; i < weights.Length; i++) { for (int j = capacity; j >= weights[i]; j--) { dp[j] = Math.Max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; }

这段代码是所有背包问题的最核心骨架。它的空间复杂度从O(n × W)降到了O(W)，时间复杂度不变，还是O(n × W)。实际跑起来，内存占用低很多，而且因为数组变小、缓存命中率更高，速度往往比二维版还要快。

3.3 遍历顺序为什么必须倒序

这个“倒序”是背包问题里面最经典的一个细节，很多讲解一句带过，但这里值得反复说清楚。

一维数组的dp[j]在更新前，其实保存的是“处理当前物品之前”的状态。如果内层正序遍历，假设当前物品重量是2、价值是3，当j = 4时，会去读dp[4 - 2] = dp[2]。问题是dp[2]可能刚刚在j = 2这一轮被更新过，它已经不是“前一个物品”时的状态了，而是“已经拿了当前物品”后的状态。于是dp[4]会基于一个已经包含当前物品的状态继续累加，结果就等价于当前物品被拿了两次以上。

倒序遍历则完全避免这个问题：从capacity往w走，更新dp[j]时，它读到的dp[j - w]下标一定比j小，而这个小的下标在当前这一轮还没被更新过，存的还是“上一个物品”状态。这样每个物品最多被选一次，正好符合0-1背包的定义。

我自己的经验是，写出正序和倒序都很容易，但如果你脑子里的模型还是“填二维表”，就很容易顺手写成正序。后来我换了个记忆方法：0-1背包每个物品只能用一次，所以一维数组从后往前更新；完全背包每个物品能用无限次，所以从前往后更新。后面讲完全背包时你会看到，这个“方向”的差别，就是两种问题的全部差别。

4. C#实现背包变体：完全背包、多重背包与分组背包

4.1 完全背包：一正序，天地宽

完全背包允许每个物品拿任意多次。在一维数组里，只需要把内层循环从倒序改成正序：

public int CompleteKnapsack(int[] weights, int[] values, int capacity) { int[] dp = new int[capacity + 1]; for (int i = 0; i < weights.Length; i++) { for (int j = weights[i]; j <= capacity; j++) { dp[j] = Math.Max(dp[j], dp[j - weights[i]] + values[i]); } } return dp[capacity]; }

注意和0-1背包唯一的区别就是内层循环的起点和方向：j从weights[i]走到capacity，递增。刚才说过，正序会让当前物品可以被反复使用，因为dp[j - w]可能已经在这一轮中被更新过，而这个更新本身就意味着“已经拿了一件当前物品”。所以当循环到j更大的位置时，dp[j - w]里可能已经堆了好几件当前物品，价值自然被叠加了。这个行为对完全背包来说正是我们想要的。

用实际场景理解一下：假设有一个物品重量10、价值20，容量是30。正序遍历到j = 20时，dp[20] = max(dp[20], dp[10] + 20)，而dp[10]已经被本轮更新成了20，所以dp[20]变成40，相当于拿了两件；到j = 30时，又会参考dp[20]变成60，相当于拿了三件。完全背包就是要这个效果。

还有一种更彻底的写法：把外层循环放在容量，内层放物品，逻辑上等价。但我觉得外层物品、内层容量的写法更容易和0-1背包对比记忆，建议守住这一套，别混用。

4.2 多重背包：用二进制拆分把数量压下来

多重背包是“每个物品最多拿c[i]个”。最朴素的想法是：把每种物品按数量展开成c[i]个独立的0-1物品，然后直接跑0-1背包。但这样物品总数会变成Σc[i]，如果每个数量都很大，O(n × c × W)可能超时。

一个常用的优化叫二进制拆分，思路是把c个物品拆成O(log c)个“捆绑包”，每个捆绑包包含1件、2件、4件、…、剩余件。比如c = 13，拆成1、2、4、6。这4个捆包能组合出0到13之间的任意数量吗？仔细试一下：1能选0或1；加2能凑0、1、2、3；加4能凑0到7；再加6，可以凑0到13。所有数量都能覆盖。

为什么拆成1, 2, 4, ...而不是1, 1, 1, ...？因为二进制分组可以用最少的组数表达任意整数，从O(c)个物品降到了O(log c)个。c = 100000时，原来要拆10万个物品，现在只需要大约17个捆绑包，量级完全不同。

C#实现如下：

private record Item(int Weight, int Value); private static List<Item> ExpandItems(int[] weights, int[] values, int[] counts) { var expanded = new List<Item>(); for (int i = 0; i < weights.Length; i++) { int w = weights[i]; int v = values[i]; int c = counts[i]; int k = 1; while (k <= c) { expanded.Add(new Item(w * k, v * k)); c -= k; k <<= 1; } if (c > 0) expanded.Add(new Item(w * c, v * c)); } return expanded; }

拆完之后，把每个Item当成0-1背包里的一个普通物品，跑一遍Knapsack01Optimized就行。注意这里每个捆绑包的重量是w * k，价值是v * k，因为捆绑包代表了“连续拿k件同类物品”的决策单元。

这种方法在面试里属于“有区分度”的考点。如果你能现场徒手写出来，面试官基本会认为你是真的理解过了，而不是背模板。

4.3 分组背包：先把一个组的决策当成“一轮”

分组背包的定义是：物品被分成若干组，每组里最多只能选一个。把它翻译成动态规划语言就是——每一轮循环处理一个组，组内所有物品共享同一组容量，只能取一个最优的。

实现套路是三层循环：外层枚举组，中层容量倒序，内层遍历组内物品。

public int GroupedKnapsack(List<List<Item>> groups, int capacity) { int[] dp = new int[capacity + 1]; foreach (var group in groups) { for (int j = capacity; j >= 0; j--) { foreach (var item in group) { if (j >= item.Weight) { dp[j] = Math.Max(dp[j], dp[j - item.Weight] + item.Value); } } } } return dp[capacity]; }

这里容量倒序的原因和0-1背包类似：组内每个物品至多选一个，不能在本轮内叠加上一个物品的状态去更新当前物品。如果正序遍历，dp[j]会同时聚合组内多个物品的价值，那就变成“组内可以选多个”了。

内层为什么要遍历组内每个物品取max？因为组内只能选一个，所以对每个容量j，你要从“不选”、“选物品A”、“选物品B”这些选项里挑一个最大的。注意这里不是比较完就立刻覆盖dp[j]，而是在整个组内所有物品都考虑过之后，dp[j]才最终确定为本组决策前的状态加上某个物品后的最优值。

分组背包在实际问题里很常见，比如“每种套餐只能选一个，每个套餐内有不同规格”，或者“每个客户类别只能推荐一款方案”。学会这一套，能处理不少真实业务场景。

5. 性能实测：暴力搜索与动态规划的真实差距

5.1 测试方案设计

光说动态规划快没有说服力，我写了一个简单的压力测试，用来对比递归暴力搜索、记忆化搜索、二维DP和一维DP。测试环境是.NET 8，Release编译，数据这样生成：物品数量n分别取20、30、50、200、1000，每个物品的重量和价值随机分布在1~100，背包容量固定为1000。

暴力搜索只测n = 20和n = 30，因为n = 50的2^50次运算在普通PC上根本不是“慢”的问题，而是直接跑不完，所以我不会让程序真的去跑。

每个方案跑完后记录耗时，取3次平均值。需要说明的是，暴力搜索和记忆化搜索用的是同一个递归函数，只是加了memo数组。

5.2 数据说话

（耗时是粗略量级，不同机器会有差异，但相对差距非常稳定。）

从这张表能看出几个明确结论。

第一，n = 30时暴力搜索已经到了40秒这个量级，动态规划还是几毫秒。这个对比太直观了：同样是求最优解，暴力要做上亿次组合计算，DP只算3万多个状态。

第二，n继续变大时，暴力搜索连测都没法测，而一维DP在n = 1000时仍然只要几十毫秒。这说明动态规划对“物品数量”的增长非常宽容，真正限制它的是n × W这个乘积。

第三，一维DP在数据量大的时候比二维DP快了不少，不仅因为内存占用小，还因为局部性更好、GC压力更小。所以工程上能写一维就不要写二维。

如果你是自己去测试，记得用Stopwatch计时，并且先做几次预热，避免第一次调用时JIT编译耗时干扰结果。这在C#性能测试里是个常见坑，我第一次测的时候把JIT时间也算进去了，数据完全没法看。

6. 常见问题与避坑清单

6.1 循环方向写反导致结果错误

这是我见过最多的问题：0-1背包的内层循环写成了正序，结果答案是“完全背包”的最优值，偏大。比如n = 2，物品分别是(w=2, v=10)、(w=3, v=15)，容量10，正确0-1背包答案应该是25（两件都拿），但如果你正序更新，dp[6]可能会被dp[4] + 10更新，而dp[4]已经是拿过第一件物品后的状态，最后算出来可能变成30以上，明显不对。

排查办法很简单：自己用笔在纸上跑一遍n = 2、W = 5的小例子，把每一轮dp数组变化画出来，一眼就能看出来方向对不对。我在实际带人的时候，发现80%的背包错误都出在这一个方向问题上。

6.2 初始化到底该用0还是负无穷

这个问题在“恰好装满”类题目里非常致命。如果题目问“恰好装满背包能获得的最大价值”，那dp[0]必须是0，dp[1..W]必须初始化为一个很大的负数，比如int.MinValue / 2，表示“用当前这些物品没办法恰好凑出这个容量”。转移时才不会拿一个“不可能状态”去更新答案。

如果题目只问“不超过容量能获得的最大价值”，那全部初始化为0就行，因为任何一个容量都可以看作“什么都不装，价值0”。

有一个很容易错的点是：用int.MinValue会溢出。如果dp[j - w]是int.MinValue，加上价值后又可能变成正数，那你就会把一个非法状态当成合法状态来更新。所以建议用int.MinValue / 2，或者直接写一个足够大的负数常量。

6.3 小细节：重量为0、大数溢出与超时陷阱

第一个坑是物品重量为0。如果某个物品w = 0、v > 0，那么一维DP无论正序还是倒序，在更新时都会出现dp[j] = max(dp[j], dp[j - 0] + v)，也就是dp[j]从自己身上加一次价值，同一轮里还会继续加。最终会把重量0的物品当作能无限拿，结果必然错误。解决办法是先把所有重量为0的物品价值累加到底数上，再对重量大于0的物品做DP。

第二个坑是大数溢出。当价值和重量都是int但单件价值很大、数量很多时，dp数组里的值可能超过int.MaxValue。这时候把dp数组声明为long[]，别硬撑着用int，否则你算出来一个负数答案，调试半天都找不到原因。

第三个坑是超时陷阱。O(n × W)在n = 2000、W = 200000时是4亿次操作，C#跑起来已经很吃力了，即使能用也可能需要十几秒。这种时候要么想办法压缩状态范围，要么换“按价值DP”的思路：把dp[v]定义为“凑到价值v所需的最小重量”，复杂度变成O(n × V)。当W远大于总价值Σv时，这种转置能救命。我在做物流系统的一个小优化时，容量字段是10亿级别，重量成本本身也很大，最后就是靠这个价值维度DP把问题化解掉的。

7. 最后一点实战心得

写到这里，背包问题的核心内容基本都覆盖了。最后分享一个我自己的体会：不要背模板，而是把“状态定义、转移方程、遍历顺序、初始化”这四个问题想清楚，再针对不同变体去调整。尤其是遍历顺序这个点，几乎每次笔试面试都会有人栽在上面，原因就是平时只顾着背代码，没有理解“倒序避免重复选、正序允许重复选”的本质。

工程上我用过最多的是0-1背包和多重背包，场景包括资源分配、装箱优化、预算裁剪等等。实际业务数据往往没那么规整，重量和价值可能是小数，重量可能是大整数，这些都需要换算和取舍。但不管怎么变，底层的DP骨架是不变的。当你第一次用动态规划把一个原本要跑几十秒的暴力枚举直接降到毫秒级，那种快感是会让人上瘾的。希望这篇文章能帮你跨过背包这道坎，往后遇到任何动态规划题，都能先想想“状态是什么、转移怎么走”，而不是急着枚举。