问题描述
有N个物品, 每个物品Cost为C[i], Value为W[i], 其中 i 属于 [0, …, N-1]
有一个书包, 容量为V
求书包能装下的最大Value
为什么叫0-1背包?
因为每个物品只有2选择: 不用(0)或者用(1). 物品不能重复使用.
暴力解法
暴力求解就是把N个物品的所有子集(Power Set)求出来, 然后看看所有Cost加起来是不是 <= 背包容量 V, 对满足以上条件的, 选出最大的Value.
子集一共有2^N个, 所以需要O(2^N)时间.
用DFS(深度优先搜索)的话, 需要O(N)空间
2维DP解法
这是一种背包固定套路, 首先初始化一个2维矩阵dp, N+1行, V+1列.
用 Python 表达出来就是
row = [0] * (1 + V)
dp = []
for i in range(N + 1):
dp.append(list(row))dp[i][v] 代表的意义是第0到第i-1个物品 (前i个物品), 容量为v的背包, 能放的最大价值
填格子的时候我们从左到右按行扫描, 也就是对一个特定物品, 第i-1个, 扫描所有可能的容量. 到第i-1个物品的时候, 容量为v的时候, 无非两种选择:
1. 把这个物品放进去, 那么v-C[i]需要大于或等于0, 否则放不下, 新的最大value为 dp[i-1][v-C[i]] + W[i]
2. 不把这个物品放进去. 为什么不放? 因为放不进了啊. value为 dp[i-1][v]
dp[i][v]需要放这两种情况中value大的那种. 用python表达就是, 先把dp[i][v]设成不放的情况, 如果可以放的话(v-C[i] >= 0), 并且放了Value增加了, 就换成放的情况. 用Python表达出来就是
for i in range(1, N + 1):
for v in range(1, V + 1):
dp[i][v] = dp[i - 1][v]
if v - C[i] >= 0:
dp[i][v] = max(
dp[i][v],
dp[i - 1][v - C[i - 1]] + W[i - 1]
)注意下标有点tricky. dp[i][v]代表的意义是前i个物品, 所以最后一个物品的index是i-1 (物品下标从0开始). 这就是为什么要用C[i - 1], W[i - 1]. 很多纯理论算法用的是1 base的index, 转换成code的时候还有点麻烦. 我这里用的就直接是Python或大部分语言能跑的真code. dp[i][j] 赋值部分就是所谓的DP转移方程.
最后把初始化, 循环和转移方程连在一起, 就可以用 Python 完整的表达出来
def maxKnapsackValue(N, C, W, V):
# init dp
row = [0] * (1 + V)
dp = []
for i in range(N + 1):
dp.append(list(row))
for i in range(1, N + 1):
for v in range(1, V + 1):
dp[i][v] = dp[i - 1][v]
if v - C[i - 1] >= 0:
dp[i][v] = max(
dp[i][v],
dp[i - 1][v - C[i - 1]] + W[i - 1]
)
return dp[N][V]以上就是 Python 版本的0-1背包问题的2维DP套路解法
2维DP解法应用
以上总结的2维DP解法的模版可以直接应用在Leetcode 416上, 详细请看这篇文章.
参考资料
崔添翼 背包问题九讲 2.0 原文有些细节讲得不清楚, 而且有些伪代码转换成真代码时候有些问题, 本文用能run的真代码并试图把细节交代清楚.
