背包问题
背包问题是动态规划的经典问题，包括 0-1 背包、完全背包和多重背包。
0-1 背包
问题描述
有 n 个物品，每个物品有重量 w[i] 和价值 v[i]，背包容量为 C。 每个物品只能选或不选，求最大价值。
实现
python
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if j < weights[i - 1]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
# 示例
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print("0-1 背包最大价值:", knapsack_01(weights, values, capacity)) # 10空间优化
python
def knapsack_01_optimized(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
# 示例
print("0-1 背包最大价值(优化):", knapsack_01_optimized(weights, values, capacity)) # 10完全背包
问题描述
有 n 种物品，每种物品有重量 w[i] 和价值 v[i]，背包容量为 C。 每种物品可以选多次，求最大价值。
实现
python
def knapsack_unbounded(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for j in range(weights[i], capacity + 1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
# 示例
weights = [2, 3, 4]
values = [3, 4, 5]
capacity = 8
print("完全背包最大价值:", knapsack_unbounded(weights, values, capacity)) # 12多重背包
问题描述
有 n 种物品，每种物品有重量 w[i]、价值 v[i] 和数量 c[i]，背包容量为 C。 每种物品最多选 c[i] 次，求最大价值。
实现
python
def knapsack_multiple(weights, values, counts, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for j in range(capacity, weights[i] - 1, -1):
for k in range(1, counts[i] + 1):
if j >= k * weights[i]:
dp[j] = max(dp[j], dp[j - k * weights[i]] + k * values[i])
return dp[capacity]
# 示例
weights = [2, 3]
values = [3, 4]
counts = [3, 2]
capacity = 8
print("多重背包最大价值:", knapsack_multiple(weights, values, counts, capacity)) # 13复杂度分析
| 问题类型 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 0-1 背包 | O(nC) | O(C) |
| 完全背包 | O(nC) | O(C) |
| 多重背包 | O(nCk) | O(C) |
应用场景
- 资源分配问题
- 投资组合优化
- 货物装载问题