动态规划解密（C#实现0-1背包问题的高效优化）

暴力解法 vs 动态规划

最直观的想法是：枚举所有可能的物品组合（共 2^n 种），然后找出满足容量限制且价值最大的组合。但当 n 很大时（比如 n=30），这种方法就完全不可行了。

而动态规划通过记忆化避免重复计算，将时间复杂度从指数级降到多项式级别！

动态规划思路解析

我们定义一个二维数组 dp[i][w]，表示：
从前 i 件物品中选择，且背包容量为 w 时，能获得的最大价值。

状态转移方程如下：

if (当前物品重量 > 当前容量 w) {    dp[i][w] = dp[i-1][w]; // 不能选，继承上一行} else {    dp[i][w] = Math.Max(        dp[i-1][w],                    // 不选第 i 件        dp[i-1][w - weight[i]] + value[i]  // 选第 i 件    );}

C# 基础实现（二维DP）

public static int Knapsack(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++)    {        for (int w = 0; w <= capacity; w++)        {            if (weights[i - 1] > w)            {                dp[i, w] = dp[i - 1, w];            }            else            {                dp[i, w] = Math.Max(                    dp[i - 1, w],                    dp[i - 1, w - weights[i - 1]] + values[i - 1]                );            }        }    }    return dp[n, capacity];}

这个实现清晰易懂，但空间复杂度是 O(n × W)，当容量 W 很大时（比如 10^6），内存可能不够用。

优化：空间压缩到一维

观察发现：计算 dp[i][w] 时，只依赖于上一行 dp[i-1][...] 的数据。因此，我们可以用一维数组来代替二维数组，从而将空间复杂度优化为 O(W)。

关键点：**内层循环必须从后往前遍历容量**，避免覆盖还未使用的旧值。

public static int KnapsackOptimized(int[] weights, int[] values, int capacity){    int[] dp = new int[capacity + 1];    for (int i = 0; i < weights.Length; i++)    {        // 从后往前遍历容量        for (int w = capacity; w >= weights[i]; w--)        {            dp[w] = Math.Max(dp[w], dp[w - weights[i]] + values[i]);        }    }    return dp[capacity];}

为什么这是 C# 算法优化 的典范？

上述优化不仅节省了大量内存，还提升了缓存局部性，使程序运行更快。这种“滚动数组”技巧在处理动态规划问题时非常常见，也是面试和竞赛中的高频考点。

总结

• 0-1背包 是理解动态规划的绝佳入口；
• 先写出二维 DP 表，理清状态转移逻辑；
• 再通过空间压缩优化到一维，提升效率；
• 掌握这一模式，可迁移到其他C#算法优化场景。

希望这篇教程能帮你彻底搞懂背包问题！动手写一遍代码，你会理解得更深刻。加油，未来的算法高手！