背包问题模板

一句话说明

背包问题是动态规划的经典问题，核心是选或不选的决策。

💻 模板代码

🎯 背包问题分类

类型	特点	遍历顺序	状态转移
0-1背包	每个物品选一次	后向前	max(dp[c], dp[c-w]+v)
完全背包	每个物品选无限次	前向后	max(dp[c], dp[c-w]+v)
多重背包	每个物品选k次	二进制优化	转化为0-1背包
分组背包	每组最多选一个	后向前	枚举组内物品

🎯 经典变形

💡 解题技巧

Go 代码

// 0-1背包
func knapsack01(weights, values []int, capacity int) int {
    dp := make([]int, capacity+1)
 
    for i := 0; i < len(weights); i++ {
        for c := capacity; c >= weights[i]; c-- {
            dp[c] = max(dp[c], dp[c-weights[i]]+values[i])
        }
    }
 
    return dp[capacity]
}
 
// 完全背包
func knapsackComplete(weights, values []int, capacity int) int {
    dp := make([]int, capacity+1)
 
    for i := 0; i < len(weights); i++ {
        for c := weights[i]; c <= capacity; c++ {
            dp[c] = max(dp[c], dp[c-weights[i]]+values[i])
        }
    }
 
    return dp[capacity]
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

---

返回：算法模板