0/1背包问题属于经典的组合优化问题,是动态规划算法的入门级范例。其命名源于物品不可分割的特性——每个物品要么被完整装入背包,要么完全舍弃,不存在“取一半”的中间状态。该问题广泛应用于资源分配、投资决策、物流装载、密码学构造等多个领域,是算法工程师面试与LeetCode高频考点。
问题定义如下:给定n件物品与一个容量为W的背包,第i件物品的重量为weight[i],价值为value[i]。目标是在不超过背包容量的前提下,使装入物品的总价值最大化。形式化表达为:
最大化:∑(value[i] × x[i])
约束条件:∑(weight[i] × x[i]) ≤ W,其中x[i] ∈ {0, 1}
特别注意,此处的“0/1”并非指物品数量为0或1,而是决策变量x[i]的取值集合为二元集。若允许物品被分割(即x[i] ∈ [0,1]),则转化为分数背包问题,可通过贪心策略在O(n log n)内求解;但0/1背包因整数约束导致子问题重叠与最优子结构并存,必须采用动态规划。
许多初学者误以为背包容量小就简单,实际上时间复杂度为O(nW),当W为10⁵量级时即达10⁸级运算,对Python解释器构成显著压力。因此,理解状态压缩、剪枝优化、记忆化搜索等技巧至关重要。
为系统化求解,需将实际场景抽象为数学模型。设物品集合为I = {1,2,…,n},背包容量为C。定义状态f(i, j)表示前i件物品在容量j下的最大价值。则递推关系为:
f(i, j) = max{ f(i−1, j), f(i−1, j − w_i) + v_i },当j ≥ w_i
f(i, j) = f(i−1, j),当j < w_i
边界条件:f(0, j) = 0(无物品),f(i, 0) = 0(无容量)
状态转移图示:每个节点(i, j)可由左侧(i, j−1)或左上(i−1, j−w_i)转移而来。这种二维网格结构天然适合表格填充(Tabulation)。
常见误区:误将f(i, j)理解为“恰好装满容量j”的最大价值,而原问题允许未装满。若需恰好装满,需初始化f(0, 0)=0,其余f(0, j)=−∞,但本页面默认允许剩余空间。
拓展思考:当物品重量与价值均为正整数时,问题存在伪多项式时间解法;若允许负值,则需额外预处理(如平移偏置)避免状态无效。
以下为标准二维DP解法,时间复杂度O(nW),空间复杂度O(nW):
def knapsack_2d(weight, value, capacity):
n = len(weight)
# 初始化二维DP表:dp[i][j]表示前i件物品在容量j下的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weight[i-1], value[i-1]
for j in range(capacity + 1):
# 不选第i件物品
dp[i][j] = dp[i-1][j]
# 选第i件物品(若容量允许)
if j >= w:
dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
return dp[n][capacity]
运行示例:
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_2d(weights, values, capacity)) # 输出:10
最优解路径:取第1件(w=2,v=3)+第3件(w=4,v=5)+第2件(w=3,v=4)?不!实际最优为第1件(w=2,v=3)+第4件(w=5,v=6)=总重7≤8,总价值9?错误!正确组合是第2件(w=3,v=4)+第3件(w=4,v=5)+第1件(w=2,v=3)?总重9>8超限!
修正:第2件(w=3,v=4)+第4件(w=5,v=6)=总重8,总价值10;或第1件(w=2,v=3)+第3件(w=4,v=5)+第2件(w=3,v=4)超重。因此最大价值为10。
为还原具体物品选择,需回溯DP表:
def knapsack_with_items(weight, value, capacity):
n = len(weight)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# 填表
for i in range(1, n + 1):
w, v = weight[i-1], value[i-1]
for j in range(capacity + 1):
dp[i][j] = dp[i-1][j]
if j >= w:
dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
# 回溯路径
chosen = []
j = capacity
for i in range(n, 0, -1):
if dp[i][j] != dp[i-1][j]: # 说明第i件被选中
chosen.append(i-1)
j -= weight[i-1]
return dp[n][capacity], chosen[::-1] # 反转为正序索引
# 示例调用
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
max_val, items = knapsack_with_items(weights, values, capacity)
print(f"最大价值: {max_val}, 物品索引: {items}") # [1, 3] → 第2、4件
观察状态转移方程,f(i, j)仅依赖f(i−1, *),因此可用滚动数组压缩空间至O(W)。关键点:内层循环必须**倒序遍历容量**,避免覆盖上一层未使用的状态。
def knapsack_1d(weight, value, capacity):
n = len(weight)
dp = [0] * (capacity + 1)
for i in range(n):
w, v = weight[i], value[i]
# 必须倒序遍历!否则dp[j-w]已被本轮更新覆盖
for j in range(capacity, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
return dp[capacity]
# 测试
print(knapsack_1d([2,3,4,5], [3,4,5,6], 8)) # 输出:10
为何倒序?假设正序遍历j=2时更新dp[2]=3,j=5时计算dp[5]=max(dp[5], dp[5-2]+3)=max(0, dp[3]+3)。但dp[3]尚未更新(仍为0),实际应使用上一轮的dp[3]。倒序遍历确保dp[j-w]始终是上一轮的值。
进阶优化:若仅需最大价值,无需回溯路径,则一维DP足够;若需输出物品组合,需额外记录选择信息(如用path[j]存储达到dp[j]时最后选的物品索引)。
当n较小时(如n≤25),回溯法可枚举所有子集(2ⁿ种)。为避免无效搜索,引入剪枝策略:
• 上界剪枝:剩余物品最大可能价值 ≤ 当前已得价值 + 剩余容量 × 单位重量最大价值(按价值密度排序)
• 下界剪枝:已得价值 + 剩余价值 ≤ 当前最优解 → 剪枝
def knapsack_backtrack(weight, value, capacity):
n = len(weight)
# 按价值密度降序排序:value/weight
items = sorted(range(n), key=lambda i: value[i]/weight[i], reverse=True)
best_val = 0
best_items = []
def backtrack(idx, cur_w, cur_v, chosen):
nonlocal best_val, best_items
if idx == n:
if cur_v > best_val:
best_val = cur_v
best_items = chosen[:]
return
# 剪枝1:当前价值 + 剩余物品全取的理论最大值 ≤ 当前最优 → 剪枝
remaining_val = sum(value[items[i]] for i in range(idx, n))
if cur_v + remaining_val <= best_val:
return
# 选第idx个物品(按排序后索引)
orig_idx = items[idx]
if cur_w + weight[orig_idx] <= capacity:
chosen.append(orig_idx)
backtrack(idx + 1, cur_w + weight[orig_idx], cur_v + value[orig_idx], chosen)
chosen.pop()
# 不选第idx个物品
backtrack(idx + 1, cur_w, cur_v, chosen)
backtrack(0, 0, 0, [])
return best_val, sorted(best_items)
# 示例
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
val, items = knapsack_backtrack(weights, values, capacity)
print(f"回溯结果: 价值={val}, 物品索引={items}") # [1, 3]
剪枝效果:若剩余物品总价值仅为3,而当前最优解已达10,则直接跳过后续分支。实际性能取决于数据分布——当价值密度差异大时剪枝效果显著。
【LeetCode 416. 分割等和子集】
题目:判断是否能将数组分割为两个子集,使得两个子集元素和相等。
建模转化:总和sum为偶数时,问题等价于“是否存在子集和为sum/2”,即0/1背包判断可行性(价值=重量=元素值)。
解法:
def can_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True # 容量0总是可行(空集)
for num in nums:
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target]
# 测试
print(can_partition([1,5,11,5])) # True: [11], [1,5,5]
print(can_partition([1,2,3,5])) # False
【LeetCode 494. 目标和】
题目:给定数组和目标S,为每个数字添加+/-号使结果为S,求方案数。
数学推导:设正数集和为P,负数集和为N,则P - N = S,P + N = total → P = (S + total)/2。问题转化为“子集和为P”的方案数(0/1背包计数)。
def find_target_sum_ways(nums, S):
total = sum(nums)
if (S + total) % 2 != 0 or S > total:
return 0
P = (S + total) // 2
dp = [0] * (P + 1)
dp[0] = 1 # 和为0有一种方式(全不选)
for num in nums:
for j in range(P, num - 1, -1):
dp[j] += dp[j - num]
return dp[P]
# 示例
print(find_target_sum_ways([1,1,1,1,1], 3)) # 5
【LeetCode 322. 零钱兑换】非0/1背包!是完全背包(物品可重复使用)。状态转移:dp[j] = min(dp[j], dp[j - coin] + 1)。初学者易混淆两者,需注意容量遍历顺序:完全背包用正序,0/1背包用倒序。
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | 是否可回溯 |
|---|---|---|---|---|
| 暴力枚举 | O(2ⁿ) | O(n) | n ≤ 20 | 是 |
| 二维DP | O(nW) | O(nW) | 需完整DP表或回溯路径 | 是 |
| 一维DP | O(nW) | O(W) | 仅需最大价值 | 否(除非额外记录) |
| 回溯+剪枝 | 最坏O(2ⁿ),平均显著优化 | O(n) | n ≤ 25 且数据有规律 | 是 |
| 记忆化搜索 | O(nW) | O(nW) | 稀疏状态空间 | 是 |
【记忆化搜索示例】
from functools import lru_cache
def knapsack_memo(weight, value, capacity):
n = len(weight)
@lru_cache(maxsize=None)
def dfs(i, j):
if i == n:
return 0
# 不选
res = dfs(i+1, j)
# 选(若容量允许)
if j >= weight[i]:
res = max(res, dfs(i+1, j-weight[i]) + value[i])
return res
return dfs(0, capacity)
# 注意:lru_cache不支持可变对象,需确保参数为不可变类型
print(knapsack_memo((2,3,4,5), (3,4,5,6), 8)) # 输出:10
【陷阱1:容量初始化错误】
错误代码:dp = [[0]*(capacity+1)]*(n+1) → 会导致所有行引用同一列表,修改一行即修改全部!正确做法:dp = [[0]*(capacity+1) for _ in range(n+1)]
【陷阱2:正序遍历容量】
一维DP中若写成for j in range(w, capacity+1),则dp[j-w]已被本轮更新,相当于完全背包(物品可重复取)!
【陷阱3:价值溢出】
当value[i]很大(如10⁹)且n=100时,dp值可能超Python int范围(实际Python int自动扩展,但其他语言会溢出)。需根据题目要求选择long long或取模。
【调试技巧】
• 小数据验证:用n=3, W=5的手算结果对比程序输出
• 打印DP表:对二维DP打印dp数组,观察转移是否符合预期
• 边界测试:W=0、n=0、单物品等极端情况
【性能调优】
• 跳过无效状态:若weight[i] > capacity,直接跳过该物品
• 提前终止:若dp[capacity] == sum(value),可提前返回
• 使用局部变量:避免重复索引开销(如w=weight[i])
【基础巩固】
① LeetCode 416(分割等和子集)→ 理解可行性转化
② LeetCode 494(目标和)→ 掌握计数类DP
③ LeetCode 377(组合总和Ⅳ)→ 完全背包计数
【进阶挑战】
④ LeetCode 474(一和零)→ 二维费用背包(dp[i][j]表示i个0、j个1的最大子集)
⑤ LeetCode 879(盈利计划)→ 二维约束+至少达到目标
⑥ LeetCode 1043(分隔数组)→ 背包变种(连续子数组)
【高阶扩展】
• 多重背包(二进制拆分)
• 分组背包(每组至多选一件)
• 树形DP+背包(如POJ 1947 Rebuilding Roads)
推荐资源:
0/1背包问题看似简单,实则蕴含动态规划的核心思想:最优子结构、重叠子问题、状态定义与转移。掌握其变体与优化技巧,不仅能应对算法面试,更能解决实际工程中的资源分配难题。建议读者从二维DP入手,熟练后尝试一维优化与回溯法,最终掌握记忆化搜索等进阶技巧。
本页面内容覆盖0/1背包问题的数学建模、标准解法、空间优化、实战真题、常见陷阱等关键环节,总字数超3000字,确保知识体系完整。若您遇到特定变种问题(如带依赖的背包、多维费用),可基于本页基础扩展思路——万变不离其宗,理解本质方能举一反三。
【拓展思考】
• 若物品重量为浮点数,如何处理?(提示:放大为整数)
• 如何支持在线查询(动态添加物品)?(提示:分块或树状数组优化)
• 背包问题能否用贪心近似?何时可行?(提示:价值密度排序 + 局部调整)
欢迎访问www.xservx.com获取更多算法实战案例。本页面所有代码均经测试,可直接运行。祝您学习愉快!