Go语言动态规划实战：背包问题详解（从零开始掌握01背包算法）

为什么用动态规划？

暴力枚举所有组合的时间复杂度是 O(2ⁿ)，当物品数量多时根本不可行。而动态规划通过记忆化子问题，将时间复杂度优化到 O(n × W)，其中 n 是物品数量，W 是背包容量。

Go语言实现01背包

我们用二维 DP 表来讲解思路，再优化为一维数组提升空间效率。

步骤1：定义状态

设 dp[i][w] 表示前 i 个物品，在背包容量为 w 时能获得的最大价值。

步骤2：状态转移方程

对于第 i 个物品（重量为 weight[i-1]，价值为 value[i-1]）：

• 如果不拿：dp[i][w] = dp[i-1][w]
• 如果拿（前提是 w ≥ weight[i-1]）：dp[i][w] = dp[i-1][w - weight[i-1]] + value[i-1]

取两者最大值即可。

Go代码实现（二维DP）

package mainimport "fmt"func knapsack(weights []int, values []int, capacity int) int {    n := len(weights)    // 创建二维DP表，初始化为0    dp := make([][]int, n+1)    for i := range dp {        dp[i] = make([]int, capacity+1)    }    // 填充DP表    for i := 1; i <= n; i++ {        for w := 0; w <= capacity; w++ {            // 不拿当前物品            dp[i][w] = dp[i-1][w]            // 如果能拿，尝试拿            if w >= weights[i-1] {                candidate := dp[i-1][w-weights[i-1]] + values[i-1]                if candidate > dp[i][w] {                    dp[i][w] = candidate                }            }        }    }    return dp[n][capacity]}func main() {    weights := []int{2, 3, 4, 5}    values := []int{3, 4, 5, 6}    capacity := 8    result := knapsack(weights, values, capacity)    fmt.Printf("最大价值为：%d\n", result) // 输出：10}

空间优化：一维DP

观察发现，dp[i][w] 只依赖于上一行 dp[i-1][...]，因此可以用一维数组从后往前更新，节省空间。

func knapsackOptimized(weights []int, values []int, capacity int) int {    dp := make([]int, capacity+1)    for i := 0; i < len(weights); i++ {        // 从后往前遍历，避免覆盖未更新的值        for w := capacity; w >= weights[i]; w-- {            if dp[w] < dp[w-weights[i]] + values[i] {                dp[w] = dp[w-weights[i]] + values[i]            }        }    }    return dp[capacity]}

关键知识点总结

• Go语言动态规划的核心在于状态定义与转移。
• 背包问题算法是理解动态规划思想的最佳起点。
• 01背包Go实现既可用二维也可用一维DP，后者更节省内存。
• 掌握动态规划入门教程中的思维模式，可迁移到其他DP问题（如完全背包、最长公共子序列等）。

结语

通过本文，你应该已经掌握了如何用 Go 语言解决 01 背包问题。动态规划看似抽象，但只要理解“子问题”和“状态转移”的思想，就能迎刃而解。动手敲一遍代码，你会理解得更深刻！

提示：在实际面试或项目中，背包问题常作为算法基础考察点，建议反复练习并尝试变种题型。