动态规划之背包问题
例题
现有4样物品n = ['a', 'b', 'c', 'd']，重量分别为w = [2, 4, 5, 3]，价值分别为v = [5, 4, 6, 2]。背包最大承重c = 9。
现求背包可以装下的最大价值。
解答
对于动态规划的三个关键要素：
-
边界。F(i, 0) = F(0, j) = 0。其中F(i, 0)代表背包此时没有空间可以容纳物品；F(0, j)代表没有物品可以放入背包。
-
最优子结构。F(i ,j)表示在前i个物品中选择，当前背包还可容纳j时的最大价值。
-
状态转移函数。
分两种情况：对于第i件物品，若此时背包没有空间可容纳可以容纳，即w[i-1]>j,此时F(i ,j) = F(i-1, j)；
若背包有能力承受第i件物品，即w[i-1]<=j，说明此时背包可以选择装入第i件物品，那么F(i, j) = F(i-1, j-w[i-1]) + v[i-1]；若背包不装入该物品，则F(i, j) = F(i-1, j)。故此时F(i, j) = max{F(i-1, j-w[i-1]) + v[i-1], F(i-1, j}。
代码
def dpsack(n, c, w, v):
recordMap = [[0 for i in range(c+1)] for i in range(len(n)+1)]
for i in range(1, len(n)+1):
for j in range(1, c+1):
if j < w[i-1]:
recordMap[i][j] = recordMap[i-1][j]
# 背包无法容纳第i件物品的时候
else:
recordMap[i][j] = max(v[i-1]+recordMap[i-1][j-w[i-1]], recordMap[i-1][j])
# 背包可容纳第i件物品的时候，选择价值最大的方式
return recordMap[len(n)][c]
# 输出矩阵右下角的元素，即为最大值。
c = 9
n = ['a', 'b', 'c', 'd']
w = [2, 4, 5, 3]
v = [5, 4, 6, 2]
dpsack(n, c, w, v)
运行结果
11
动态规划的总结
- 在给定约束条件下优化某指标，可使用动态规划
- 问题可以被分解为离散子问题时，可考虑动态规划
- 动态规划解决方案一定涉及表格
- 单元格中的值是需要优化的值
- 每个单元格都是一个子问题，所以需要考虑如何将问题分解为子问题
- 没有放之四海皆准的dp解决公式
- dp三要素：边界；最优子结构；状态转移函数