背包问题

背包问题详解

背包问题是动态规划领域的经典问题，核心思想是：在给定总容量/总预算限制下，如何选择物品，使得某个收益最大化。

物品有多种属性，在某一属性受限的情况下，另外属性能够获取的最大收益。根据物品的选择限制，背包问题主要分为三大类：

• 0-1 背包问题：每个物品要么选 0 次要么选 1 次（物品只能选一次）
• 完全背包问题：每种物品可以选择无限次
• 多重背包问题：每个物品可以选有限的多次

---

一、0-1 背包问题

问题描述：
有 N 个物品和一个容量为 W 的背包，第 i 个物品重量为 w[i]，价值为 v[i]。每个物品只能用一次。求背包能装入物品的最大价值。

动态规划核心思路

• 状态定义：
  • dp[i][j]: 前i个物品，背包容量为j时，能获得的最大价值
• 状态转移方程：

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

  选或不选第i个物品

• 初始条件：
  • dp[0][j] = 0
• 目标：
  • dp[N][W]，即全部物品考虑完，容量为W时的最大价值

优化（空间压缩）

可以将二维 dp[i][j] 优化为一维 dp[j]，且需倒序遍历容量：

for i := 1 to N
    for j := W downto w[i]
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

Go 代码示例

package main

import "fmt"

// 0-1 背包问题：空间优化版本
func knapsack01(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([]int, capacity+1)
    
    for i := 0; i < n; i++ {
        // 倒序遍历，避免覆盖需要使用的历史状态
        for j := capacity; j >= weights[i]; j-- {
            if dp[j] < dp[j-weights[i]]+values[i] {
                dp[j] = dp[j-weights[i]] + values[i]
            }
        }
    }
    return dp[capacity]
}

// 0-1 背包问题：二维DP版本（便于理解）
func knapsack01_2D(weights, values []int, capacity int) int {
    n := len(weights)
    // dp[i][w] 表示前i个物品，在容量为w的背包中能获得的最大价值
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }
    
    for i := 1; i <= n; i++ {
        for w := 1; w <= capacity; w++ {
            // 不选第i个物品
            dp[i][w] = dp[i-1][w]
            
            // 选第i个物品（如果容量足够）
            if w >= weights[i-1] {
                if dp[i-1][w-weights[i-1]]+values[i-1] > dp[i][w] {
                    dp[i][w] = dp[i-1][w-weights[i-1]] + values[i-1]
                }
            }
        }
    }
    return dp[n][capacity]
}

// 0-1 背包问题：返回具体选择的物品
func knapsack01WithPath(weights, values []int, capacity int) (int, []int) {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }
    
    // 记录选择路径
    choice := make([][]bool, n+1)
    for i := range choice {
        choice[i] = make([]bool, capacity+1)
    }
    
    for i := 1; i <= n; i++ {
        for w := 1; w <= capacity; w++ {
            dp[i][w] = dp[i-1][w]
            
            if w >= weights[i-1] {
                if dp[i-1][w-weights[i-1]]+values[i-1] > dp[i][w] {
                    dp[i][w] = dp[i-1][w-weights[i-1]] + values[i-1]
                    choice[i][w] = true
                }
            }
        }
    }
    
    // 回溯找出选择的物品
    path := make([]int, 0)
    w := capacity
    for i := n; i > 0; i-- {
        if choice[i][w] {
            path = append(path, i-1)
            w -= weights[i-1]
        }
    }
    
    return dp[n][capacity], path
}

func main() {
    weights := []int{2, 3, 4, 5}
    values := []int{3, 4, 5, 6}
    capacity := 8
    
    maxValue := knapsack01(weights, values, capacity)
    fmt.Printf("最大价值: %d\n", maxValue)
    
    maxValue2, path := knapsack01WithPath(weights, values, capacity)
    fmt.Printf("最大价值: %d, 选择的物品索引: %v\n", maxValue2, path)
    
    // 输出:
    // 最大价值: 10
    // 最大价值: 10, 选择的物品索引: [2 1]
}

时间复杂度：O(n × W)，其中 n 是物品数量，W 是背包容量
空间复杂度：O(W)（一维优化）或 O(n × W)（二维版本）

---

二、完全背包问题

问题描述：
有 N 个物品和背包容量 W，每个物品有无限多个。第i个物品重量w[i]，价值v[i]。问最大可装价值。

动态规划核心思路

• 状态定义：同上
• 状态转移方程：

  dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

  因为物品可选多次，dp[i][…] 依赖前面的 dp[i][…]

• 优化后转移（可使用一维数组且正序遍历）：

for i := 1 to N
    for j := w[i] to W
        dp[j] = max(dp[j], dp[j-w[i]]+v[i])

Go 代码示例

package main

import "fmt"

// 完全背包问题：正序遍历
func completeKnapsack(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([]int, capacity+1)
    
    for i := 0; i < n; i++ {
        // 正序遍历，允许同一物品多次选择
        for j := weights[i]; j <= capacity; j++ {
            if dp[j] < dp[j-weights[i]]+values[i] {
                dp[j] = dp[j-weights[i]] + values[i]
            }
        }
    }
    return dp[capacity]
}

// 完全背包问题：二维DP版本
func completeKnapsack_2D(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }
    
    for i := 1; i <= n; i++ {
        for w := 1; w <= capacity; w++ {
            // 不选第i个物品
            dp[i][w] = dp[i-1][w]
            
            // 选第i个物品（可以选多次，所以依赖dp[i][w-weights[i-1]]）
            if w >= weights[i-1] {
                if dp[i][w-weights[i-1]]+values[i-1] > dp[i][w] {
                    dp[i][w] = dp[i][w-weights[i-1]] + values[i-1]
                }
            }
        }
    }
    return dp[n][capacity]
}

func main() {
    weights := []int{2, 3, 4}
    values := []int{3, 4, 5}
    capacity := 8
    
    maxValue := completeKnapsack(weights, values, capacity)
    fmt.Printf("完全背包最大价值: %d\n", maxValue)
    
    // 输出: 完全背包最大价值: 12
    // 说明: 可以选择物品0（重量2，价值3）4次，总价值12
}

时间复杂度：O(n × W)
空间复杂度：O(W)（一维优化）或 O(n × W)（二维版本）

关键区别：与 0-1 背包的区别在于遍历顺序

• 0-1 背包：倒序遍历（j--），确保每个物品只用一次
• 完全背包：正序遍历（j++），允许同一物品多次选择

---

三、多重背包问题

问题描述：
有 N 个物品和背包容量 W，第 i 个物品最多可选 s[i] 次，重量为 w[i]，价值为 v[i]。求最大可装价值。

解法一：直接拆解（朴素方法）

将每个物品拆解成 s[i] 个独立的物品，转化为 0-1 背包问题。

解法二：二进制优化（推荐）

使用二进制拆分，将物品数量从 s[i] 优化到 log(s[i]) 个物品。

二进制拆分原理：

• 将数量 s 拆分为：1, 2, 4, 8, …, 2^k, s - 2^(k+1) + 1
• 这些数可以组合出 0 到 s 之间的任意数量
• 例如：s = 10，拆分为 1, 2, 4, 3（可以组合出 0-10）

Go 代码示例

package main

import "fmt"

// 多重背包问题：二进制优化
func multipleKnapsack(weights, values, counts []int, capacity int) int {
    n := len(weights)
    
    // 二进制拆分
    newWeights := make([]int, 0)
    newValues := make([]int, 0)
    
    for i := 0; i < n; i++ {
        // 对每个物品进行二进制拆分
        count := counts[i]
        k := 1
        for k < count {
            newWeights = append(newWeights, weights[i]*k)
            newValues = append(newValues, values[i]*k)
            count -= k
            k *= 2
        }
        // 剩余部分
        if count > 0 {
            newWeights = append(newWeights, weights[i]*count)
            newValues = append(newValues, values[i]*count)
        }
    }
    
    // 转化为0-1背包问题
    dp := make([]int, capacity+1)
    for i := 0; i < len(newWeights); i++ {
        for j := capacity; j >= newWeights[i]; j-- {
            if dp[j] < dp[j-newWeights[i]]+newValues[i] {
                dp[j] = dp[j-newWeights[i]] + newValues[i]
            }
        }
    }
    return dp[capacity]
}

// 多重背包问题：直接拆解方法
func multipleKnapsackNaive(weights, values, counts []int, capacity int) int {
    n := len(weights)
    dp := make([]int, capacity+1)
    
    for i := 0; i < n; i++ {
        // 对每个物品，考虑选择0到counts[i]次
        for j := capacity; j >= weights[i]; j-- {
            for k := 1; k <= counts[i] && k*weights[i] <= j; k++ {
                if dp[j] < dp[j-k*weights[i]]+k*values[i] {
                    dp[j] = dp[j-k*weights[i]] + k*values[i]
                }
            }
        }
    }
    return dp[capacity]
}

func main() {
    weights := []int{2, 3, 4}
    values := []int{3, 4, 5}
    counts := []int{2, 3, 1} // 每个物品最多可选次数
    capacity := 8
    
    maxValue := multipleKnapsack(weights, values, counts, capacity)
    fmt.Printf("多重背包最大价值: %d\n", maxValue)
    
    // 输出: 多重背包最大价值: 11
}

时间复杂度：

• 朴素方法：O(n × W × S)，其中 S 是最大物品数量
• 二进制优化：O(n × W × log(S))

空间复杂度：O(W)

---

四、背包问题变体

1. 恰好装满背包

问题描述：判断是否能用给定物品恰好装满背包。

// 判断是否能恰好装满背包
func canFillKnapsack(weights []int, capacity int) bool {
    dp := make([]bool, capacity+1)
    dp[0] = true // 容量为0时，不选任何物品，可以装满
    
    for i := 0; i < len(weights); i++ {
        for j := capacity; j >= weights[i]; j-- {
            dp[j] = dp[j] || dp[j-weights[i]]
        }
    }
    return dp[capacity]
}

2. 装满背包的方案数

问题描述：求有多少种方法可以装满背包。

// 0-1背包：装满背包的方案数
func waysToFillKnapsack(weights []int, capacity int) int {
    dp := make([]int, capacity+1)
    dp[0] = 1 // 容量为0时，有一种方案（不选任何物品）
    
    for i := 0; i < len(weights); i++ {
        for j := capacity; j >= weights[i]; j-- {
            dp[j] += dp[j-weights[i]]
        }
    }
    return dp[capacity]
}

// 完全背包：装满背包的方案数
func waysToFillCompleteKnapsack(weights []int, capacity int) int {
    dp := make([]int, capacity+1)
    dp[0] = 1
    
    for i := 0; i < len(weights); i++ {
        for j := weights[i]; j <= capacity; j++ {
            dp[j] += dp[j-weights[i]]
        }
    }
    return dp[capacity]
}

3. 最小价值/重量

问题描述：在满足价值要求的前提下，求最小重量。

// 0-1背包：在满足价值要求下的最小重量
func minWeightKnapsack(weights, values []int, targetValue int) int {
    // dp[j] 表示价值为j时的最小重量
    dp := make([]int, targetValue+1)
    for i := range dp {
        dp[i] = 1 << 31 // 初始化为最大值
    }
    dp[0] = 0
    
    for i := 0; i < len(weights); i++ {
        for j := targetValue; j >= values[i]; j-- {
            if dp[j-values[i]] != 1<<31 {
                if dp[j] > dp[j-values[i]]+weights[i] {
                    dp[j] = dp[j-values[i]] + weights[i]
                }
            }
        }
    }
    
    if dp[targetValue] == 1<<31 {
        return -1 // 无法达到目标价值
    }
    return dp[targetValue]
}

4. 二维费用背包

问题描述：物品有两个维度的费用（如重量和体积），背包也有两个维度的容量限制。

// 二维费用背包问题
func twoDimensionalKnapsack(weights, volumes, values []int, maxWeight, maxVolume int) int {
    n := len(weights)
    // dp[i][j] 表示重量为i，体积为j时的最大价值
    dp := make([][]int, maxWeight+1)
    for i := range dp {
        dp[i] = make([]int, maxVolume+1)
    }
    
    for k := 0; k < n; k++ {
        for i := maxWeight; i >= weights[k]; i-- {
            for j := maxVolume; j >= volumes[k]; j-- {
                if dp[i][j] < dp[i-weights[k]][j-volumes[k]]+values[k] {
                    dp[i][j] = dp[i-weights[k]][j-volumes[k]] + values[k]
                }
            }
        }
    }
    return dp[maxWeight][maxVolume]
}

---

五、LeetCode 经典题目

1. 分割等和子集（LeetCode 416）

问题描述：判断是否可以将数组分割成两个子集，使得两个子集的元素和相等。

// LeetCode 416. 分割等和子集
func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum%2 != 0 {
        return false
    }
    
    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true
    
    for i := 0; i < len(nums); i++ {
        for j := target; j >= nums[i]; j-- {
            dp[j] = dp[j] || dp[j-nums[i]]
        }
    }
    return dp[target]
}

2. 目标和（LeetCode 494）

问题描述：给定一个非负整数数组和目标值，通过添加 + 或 - 使表达式等于目标值，求方案数。

// LeetCode 494. 目标和
func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    
    diff := sum - target
    if diff < 0 || diff%2 != 0 {
        return 0
    }
    
    neg := diff / 2
    dp := make([]int, neg+1)
    dp[0] = 1
    
    for i := 0; i < len(nums); i++ {
        for j := neg; j >= nums[i]; j-- {
            dp[j] += dp[j-nums[i]]
        }
    }
    return dp[neg]
}

3. 零钱兑换（LeetCode 322）

问题描述：给定不同面额的硬币和总金额，计算可以凑成总金额的最少硬币数。

// LeetCode 322. 零钱兑换（完全背包）
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1 // 初始化为不可能的大值
    }
    dp[0] = 0
    
    for i := 0; i < len(coins); i++ {
        for j := coins[i]; j <= amount; j++ {
            if dp[j] > dp[j-coins[i]]+1 {
                dp[j] = dp[j-coins[i]] + 1
            }
        }
    }
    
    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

4. 零钱兑换 II（LeetCode 518）

问题描述：给定不同面额的硬币和总金额，计算可以凑成总金额的硬币组合数。

// LeetCode 518. 零钱兑换 II（完全背包方案数）
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    
    for i := 0; i < len(coins); i++ {
        for j := coins[i]; j <= amount; j++ {
            dp[j] += dp[j-coins[i]]
        }
    }
    return dp[amount]
}

5. 一和零（LeetCode 474）

问题描述：给定二进制字符串数组，找到最多 m 个 0 和 n 个 1 的最大子集大小。

// LeetCode 474. 一和零（二维费用背包）
func findMaxForm(strs []string, m int, n int) int {
    // dp[i][j] 表示使用i个0和j个1能组成的最大字符串数量
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    
    for _, str := range strs {
        zeros, ones := countZerosOnes(str)
        for i := m; i >= zeros; i-- {
            for j := n; j >= ones; j-- {
                if dp[i][j] < dp[i-zeros][j-ones]+1 {
                    dp[i][j] = dp[i-zeros][j-ones] + 1
                }
            }
        }
    }
    return dp[m][n]
}

func countZerosOnes(s string) (int, int) {
    zeros, ones := 0, 0
    for _, ch := range s {
        if ch == '0' {
            zeros++
        } else {
            ones++
        }
    }
    return zeros, ones
}

---

六、背包问题总结

核心要点

1. 0-1 背包：倒序遍历容量（j--），确保每个物品只用一次
2. 完全背包：正序遍历容量（j++），允许同一物品多次选择
3. 多重背包：使用二进制优化，将物品数量从 O(s) 优化到 O(log s)
4. 背包问题的本质：约束条件下的子集选取

状态转移方程对比

问题类型	状态转移	遍历顺序
0-1 背包	dp[j] = max(dp[j], dp[j-w[i]] + v[i])	倒序 j--
完全背包	dp[j] = max(dp[j], dp[j-w[i]] + v[i])	正序 j++
多重背包	二进制优化后转为 0-1 背包	倒序 j--

常见变体

• 恰好装满：初始化 dp[0] = true/1，其他为 false/0
• 方案数：将 max 改为 +，dp[0] = 1
• 最小价值/重量：将 max 改为 min，初始化最大值
• 二维费用：增加一维状态

时间复杂度

• 0-1 背包：O(n × W)
• 完全背包：O(n × W)
• 多重背包：O(n × W × log S)（二进制优化）

空间优化技巧

• 使用一维数组代替二维数组
• 注意遍历顺序（0-1 背包倒序，完全背包正序）

---

参考文献

• LeetCode 背包问题专题
• 《算法导论》第 16 章
• 《背包九讲》- 崔添翼