一种方法解决所有背包问题
本文首发于微信公众号《前端和大数据》
背包问题是一种特定的最优化问题. 在业务和面试中都很常见. 这个问题的形式通常是：给定一组物品，每个物品都有相应的重量和价值，目标是在不超过背包容量限制的情况下，选择部分（或全部）物品，使总价值最大。
解决背包问题, 通常需要用动态规划的方法.
现实中的应用场景
在现实中有如下很多实际应用场景
- 物流与供应链：在决定要运送哪些货物时，可能需要考虑每个货物的价值和重量（或体积）来最大化装载价值。
- 资源分配：在有限的预算下，如何为多个项目分配资金以达到最大收益。
- 电力管理：在数据中心等环境中，如何根据设备功耗和计算效率分配电力，以获得最大的计算效果。
- 投资组合优化：在考虑投资组合时，投资者可能希望在风险和回报之间找到平衡。这可以视为一个背包问题，其中项的权重是风险，值是预期回报。
- 工作调度：在给定资源限制的情况下，如何安排任务以使利润最大化。
- 指标优化：在网络设计或其他工程领域，可能需要在满足一定约束条件下选择一组参数或元素，以优化某些性能指标。
背包问题的类型
根据对数量的限制背包问题有3种类型
- 0-1背包问题：每种物品只有一个，可以选择放入或不放入, 没有中间态。
- 完全背包问题：每种物品有无限个，可以任意选择数量放入。
- 多重背包问题：每种物品有限定数量，可以选择部分数量放入。
通用解决思路
背包问题也是动态规划问题, 因此可以采用动态规划的一般流程解决.
- 定义子问题：将原问题分解为更小的、更易于管理的部分。这些子问题通常是重复出现并且独立的。
- 构建DP表格/数组：创建一个表格或数组来存储每个子问题的答案。多数情况下，该表格/数组是从最简单的基础情况逐步构建起来的。
- 初始状态设定：确定并设置基础子问题的解。对于很多问题，这一步可能涉及到初始化DP表格/数组的边界值。
- 状态转移方程定义：找出一个公式或者方法，用于通过已知的子问题的解计算其他子问题的解。
- 代码实现：使用动态规划表格/数组求解原问题。这通常涉及到从表格/数组中读取或汇总信息。
- 定义 bad case
标准的背包问题
如下是一个标准的背包问题
有5个物品, 重量分别是 1kg, 1kg, 2kg, 10kg, 12kg 他们的价值分别是 1, 2, 2, 10, 4. 把他们装到容量为15kg 的背包中, 能装的最大金额是多少?
[[Pasted image 20230818163725.png]]
按通用解决思路分析:
- 定义子问题 对于前 i 个物品, 当限重为 j 时的最大价值
- 构建 DP 表格 横坐标为包的限重, 总坐标为前 i 个物品
包的限重为j时
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 0 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3 0 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5
4 0 2 3 4 5 5 5 5 5 5 10 12 13 14 15 15
5 0 2 3 4 5 5 5 5 5 5 10 12 13 14 15 15
前i个物品
- 定义状态转换方程 每个物品有2种状态, 可以选择放入背包或不放入 不放入第i 个物品时的价值
dp[i-1][j]放入第 i 个物品时的价值为dp[i-1][j-weight[i]]+value[i]因此前 i 个物品, 限重为 j 时的最大值为
dp[i][j] = max(dp[i-1][j-weight[i]]+value[i], dp[i-1][j])
- 定义初始状态 当 i = 0 时, 即未放入物品时,
dp[0][x] = 0. 0<= x <= 包的最大限重当 j = 0 时, 即包的限重为0时, 那么所有的价值也都是 0 .dp[x][0] = 0. 0<= x <= 物品数量 - 代码实现 以下为 python 版本的实现
def knapsack(weight, value, capacity):
goods_cnt = len(weight)
dp = [[0 for _ in range(capacity + 1)]
for _ in range(goods_cnt + 1)]
for i in range(1, goods_cnt + 1):
dp[i][0] = 0
for j in range(1, capacity + 1):
if weight[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j],
dp[i - 1][j - weight[i - 1]] + value[i - 1])
return dp[goods_cnt][knapsack_capacity]
# 测试用例
1kg, 1kg, 2kg, 10kg, 12kg 他们的价值分别是 1, 2, 2, 10, 4. 把他们装到容量为15kg 的
weight, value, capacity = [1,1,2,10,12], [1,2,2,10,4], 15
knapsack(weight, value, capacity)
其他的背包问题都可以转为基于标准背包问题的形式
0-1背包(0-1 knapsack problem)
01背包是指每个物品可以选择放入或不放入背包, 只有这2种状态的情况. 标准背包也是一个01背包问题
分割等和子集
leetcode 416 题题目: 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1, 5, 4, 7, 5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [4, 7] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
解析
与标准问题不同, 该题是求价值能否刚好等于固定值, 而非物品的最大价值. 该题可以转化为求一个数组中能否找到一个子集, 使该子集的合等于整个数组的一半.
转为标准背包问题 对于示例1 , nums= [1, 5, 4, 7, 5], 可以转为如下问题 有 4 个物品, 价值 value = [1, 5, 4, 7, 5], 物品重量 weight = [1, 5, 4, 7, 5] , 背包容量为 sum(value) / 2 = 11 求能否取 n 个物品, 使其装到背包中后的总价值为 11
解题步骤:
- 定义子问题.
dp[i][j]为前 i 个物品时, 装入容量为 j 的背包时, 总价值是否为target - 构建 DP 表格
0 1 2 3 4 5 6 7 8 9 10 11 x轴表示物品总重量
0 T F F F F F F F F F F F
1 T T F F F F F F F F F F
2 T T F F F F T F F F F F
3 T T F F T T F F F F T F
4 T T F F T T F T T F F T
5 T T F F T T T T F F T T
y轴表示前i个物品
- 定义状态转换方程 与标准背包类似, 不过这里dp的值是布尔值, 表示价值是否刚好等于目标值
# i 表示前 i 个物品, j 表示背包的总重量
# dp[i][j] 表示取前 i 个物品装到容量为 j 的背包时, 总价值能否刚好等于 j
# 不装入物品 i 时, 结果为
dp[i-1][j]
# 装入物品 i 时, 结果为
dp[i-1][j-weight[i - 1]] + value[i - 1] == j
# 由于 value 与 weight 的值相同. 因此上面的公式等价于下面的
dp[i-1][j-weight[i - 1]]
# 结合这2种情况, 得到下面的方程
dp[i][j] = dp[i-1][j-weight[i - 1]] or dp[i - 1][j]
- 定义初始状态 根据定义可知 当
j = 0时,dp[i][0] = True; 0 =< i <= len(nums) - 代码实现
def canPartition(nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = int(total / 2)
n = len(nums)
# 用二维数组实现
dp = [[False for _ in range(target + 1)] for _ in range(n + 1)]
dp[0][0] = True
for i in range(1, n + 1):
dp[i][0] = True
for j in range(1, target + 1):
if nums[i - 1] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i - 1]]
return dp[n][target]
完全背包 UKP (unbounded knapsack problem)
完全背包指每种物品不限制数量的情况. 如硬币问题
硬币兑换
参考 leetcode 322 题 题目
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
解析
标准背包中的纵轴 i 表示前 i 个物品, 在完全背包中的物品数量不限, 因此 y轴不能表示前 i 个物品. 这种情况下, y轴的 i 可以定义为第 i 种物品.
转为标准背包问题:
对于示例1, coins=[1, 2, 5], amount = 11. 有一组物品, 重量 weight = [1, 2, 5] 价值 value=[1, 2, 5]. 背包容量 capacity = 11, 求装入背包的物品价值刚好等于11 时的最小物品数量
解题步骤:
- 定义子问题：
dp[i][j]表示只用[0:i]硬币, 凑到金额 j 时的最小硬币数量. - 构建DP表格/数组：
x 轴背包的容量,也等于硬币总价值
0 1 2 3 4 5 6 7 8 9 10 11
0 0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf
1 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
2 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6
3 0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3
y轴当前硬币序号
- 初始状态设定: dp初始化时默认值都设置为
float('inf'), 表示无法凑成 当j = 0时,dp[i][0] = 0 - 状态转移方程定义 当不使用该硬币时, 最小数量为 i-1时的总数量, 即
dp[i-1][j]. 总金额小于硬币面值时, 也无法使用该硬币 当使用该硬币时, 最小数量是总额小于该硬币面值时的数量 + 1,dp[i][j-value[i]] + 1得到状态方程
j < coins[i - 1] 时; dp[i][j] = dp[i-1][j]
j >= coins[i - 1] 时, dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i - 1]] + 1)
- 代码实现：
def coin_change(coins, amount):
dp = [[float('inf') for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
dp[0][0] = 0
for i in range(1, len(coins) + 1):
dp[i][0] = 0
for j in range(1, amount + 1):
coin = coins[i - 1]
if coin > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = min(dp[i-1][j-coin] + 1,
dp[i-1][j], dp[i][j - coin] + 1)
return dp[len(coins)][amount]
多重背包BKP (bounded knapsack problem)
每种物品有限定的数量. 求最大价值
盗窃最大价值
题目
一个盗贼，闯进了一个商场，准备偷窃一些物品。你有一个背包，容量为10千克。商场中有如下物品可供选择：
1. 键盘, 重量1千克, 总共有3台, 每个价值6美元。
2. 音响, 重量2千克, 总共有2个, 每个价值10美元。
3. 笔记本电脑, 重量3千克, 总共有1台, 价值12美元。
每种物品数量有限。目标是选择一部分物品放入背包中，使得背包中的物品总价值最大，同时不超过背包的容量。
问题：盗贼应该选择哪些物品，以及每种物品应该选择多少，才能在不超过背包容量的前提下，使得背包中的物品总价值最大？
解析 该情况的特殊之处在于数量是有限的, 且大于等于 1 . 因此无法使用 01背包或完全背包的方式解决. 需要对01背包进行变形. 还是把 dp[i][j] 的值定义为前 i 个物品, 限重为 j 的背包时的最大价值 但是在计算 dp[i][j] 时, 需要依次遍历可能的数量, 获取最大价值
- 定义子问题 前 i 件物品放入容量为 j 的背包时的最大价值等于放入数量依次为 [0: counts[i]] 时的最大值
- 构建DP表格/数组 按示例的问题. weights, values, counts = [1, 2, 3], [6, 10, 12], [3, 2, 1] 背包容量 capacity = 10
0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0
1 0 6 12 18 18 18 18 18 18 18 18
2 0 6 12 18 22 28 32 38 38 38 38
3 0 6 12 18 22 28 32 38 40 44 50
- 初始状态设定 当 i = 0 或 j = 0 时, dp[i][j] = 0
- 状态转移方程定义： 令
dp[i][j]表示前 i 件物品放入容量为 j 的背包时的最大价值 令 k 表示第 i 个物品取的数量为 kj < weight[k]时:dp[i][j] = dp[i - 1][j]j >= weight[k]时, k 个物品的最大价值为dp[i - 1][j - weights[i - 1] * k] + values[i - 1] * k. 则
for k in range(0, counts[i - 1]):
dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i - 1] * k] + values[i - 1] * k)
- 代码实现：
def bkp(weights, values, counts, capacity):
weights = [0] + weights # 头部补 0, 方便计算
values = [0] + values # 头部补 0, 方便计算
counts = [0] + counts # 头部补 0, 方便计算
dp = [[0 for _ in range(capacity + 1)] for _ in range(len(weights))]
for i in range(1, len(weights)):
for j in range(1, capacity + 1):
for k in range(1, counts[i] + 1):
if weights[i] * k > j:
dp[i][j] = max(dp[i-1][j], dp[i][j], dp[i][j - 1])
else:
dp[i][j] = max(dp[i-1][j - weights[i] * k] +
values[i] * k, dp[i][j])
return dp[-1][-1]
总结
从物品数量限制的维度背包问题可以分为本文的3种情况, 都可以转为标准的背包问题.
但是初次之外还有其他背包类型的问题, 如多维背包, 即物品有多个维度, 背包有多个维度限制, 如需要同时满足体积和重量. 但是解决的步骤类似, 能列出 DP 表格之后, 通常可以找到规律. 并得到动态转移方程
本文使用 markdown.com.cn 排版
