C#动态规划之背包问题求解（从零开始掌握01背包算法）

为什么用动态规划？

暴力枚举所有可能的组合虽然可行，但时间复杂度是 O(2^n)，当物品数量稍大时就不可行了。而动态规划通过记忆化子问题，将时间复杂度优化到 O(n * W)，效率大大提升。

C#实现01背包问题

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

步骤解析：

1. 初始化一个 (n+1) x (W+1) 的二维数组，全部设为0。
2. 遍历每个物品（从1到n）。
3. 对每个可能的背包容量（从0到W）进行判断：
• 如果当前物品重量 > 当前容量，则不能放入，继承上一行的值。
• 否则，取“放入”和“不放入”的最大值。

C#代码实现：

public static int Knapsack01(int[] weights, int[] values, int capacity){    int n = weights.Length;    // 创建 dp 表，dp[i][w] 表示前 i 个物品在容量 w 下的最大价值    int[,] dp = new int[n + 1, capacity + 1];    // 填充 dp 表    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];}

使用示例：

static void Main(string[] args){    int[] weights = { 2, 1, 3, 2 };    int[] values  = { 12, 10, 20, 15 };    int capacity = 5;    int maxValue = Knapsack01(weights, values, capacity);    Console.WriteLine($"最大价值为: {maxValue}"); // 输出：37}

优化空间复杂度（进阶）

上述方法使用了 O(n * W) 的空间。其实我们只需要一维数组即可，因为每次只依赖上一行的数据。以下是空间优化版：

public static int Knapsack01Optimized(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#动态规划 解决经典的 01背包问题。这不仅是面试高频题，也是理解动态规划思想的绝佳入口。记住核心思想：将大问题分解为子问题，并保存子问题的解避免重复计算。

希望这篇 C#算法教程 能帮助你打下坚实的算法基础。动手敲一遍代码，你会理解得更深刻！

关键词回顾：C#动态规划、背包问题、C#算法教程、01背包问题求解