首先通过求解0-1背包问题的思路演化来引出动态规划的方法。
0-1背包
假设我们有一个最大负重量为9的背包，同时我们有5个物品，每个物品的重量分别为2，2，4，6，3。且物品不可拆卸，也就是说我们要么将一个物品全部放入背包，要么全部不放。那么，请问，我们最大能装多大重量的物品进入背包？
1. 回溯思想求解0-1背包
首先我们用回溯的思想求解这个问题，代码如下。
回溯本质上可以理解为一种穷举所有可能的路径，如果不满足要求，迅速结束此路径的探索。
# 0-1背包问题
weight = [2, 2, 4, 6, 3]
n = 5
max_allowed_weight = 9
cur_max_weight = -1
class ZeroOneBag(object):
def __init__(self, weight, n, max_allowed_weight, cur_max_weight):
self.weight = weight
self.n = n
self.max_allowed_weight = max_allowed_weight
self.cur_max_weight = cur_max_weight
def backtracking(self, i, cur_weight, cur_result):
"""
# 将物品一个一个的做判定，当判定到第i个物品当前背包重量为cur_weight时候的情况
# 初始调用backtrack(0,0)
"""
if i == n or cur_weight == self.max_allowed_weight:
if cur_weight > self.cur_max_weight:
self.cur_max_weight = cur_weight
if sum(cur_result) == self.cur_max_weight:
print('result, cur_max_weight', cur_result, self.cur_max_weight)
return
# 不加入第i个物品
cur_result.append(0)
self.backtracking(i+1, cur_weight, list(cur_result))
# 若背包重量允许，则加入第i个物品
if cur_weight + self.weight[i] <= self.max_allowed_weight:
cur_result.pop(-1)
cur_result.append(weight[i])
self.backtracking(i+1, cur_weight + weight[i], list(cur_result))
if __name__ == '__main__':
# 0-1背包问题
weight = [2, 2, 4, 6, 3]
n = 5
max_allowed_weight = 9
cur_max_weight = -1
p = ZeroOneBag(weight, n, max_allowed_weight, cur_max_weight)
p.backtracking(0, 0, [])
总共有19种结果：
image.png
实际上满足要求的只有5种解法：
image.png
2. 备忘录优化重复计算
因为这个求解过程是一个递归，所以我们可以画出其对应的递归树，从而帮助我们理解。
递归树
递归树的每个节点表示一个状态。可以用f(i, cur_weight)表示，i表示放入或不放入第i个物品后，背包当前的总重量。
从图中我们可以看出，存在着较多的没有必要的重复计算。比如，对于f(2, 2)来说，从结果上看，我们并不关心经过前2个物品的判定后结果为2的具体组合是什么。
我们可以使用备忘录的方式避免重复计算。代码如下：
# 0-1背包问题
weight = [2, 2, 4, 6, 3]
n = 5
max_allowed_weight = 9
cur_max_weight = -1
class ZeroOneBag(object):
def __init__(self, weight, n, max_allowed_weight, cur_max_weight, flag):
self.weight = weight
self.n = n
self.max_allowed_weight = max_allowed_weight
self.cur_max_weight = cur_max_weight
self.flag = flag
def backtracking(self, i, cur_weight, cur_result):
"""
# 将物品一个一个的做判定，当判定到第i个物品当前背包重量为cur_weight时候的情况
# 初始调用backtrack(0,0)
"""
# print(i, cur_weight)
if i == n or cur_weight == self.max_allowed_weight:
if cur_weight > self.cur_max_weight:
self.cur_max_weight = cur_weight
if sum(cur_result) == self.cur_max_weight:
print('cur_result, cur_max_weight', cur_result, self.cur_max_weight)
return
if self.flag[i][cur_weight]:
return
# 不加入第i个物品
cur_result.append(0)
self.backtracking(i+1, cur_weight, list(cur_result))
# 若背包重量允许，则加入第i个物品
if cur_weight + self.weight[i] <= self.max_allowed_weight:
cur_result.pop(-1)
cur_result.append(weight[i])
self.backtracking(i+1, cur_weight + weight[i], list(cur_result))
self.flag[i][cur_weight] = True
if __name__ == '__main__':
# 0-1背包问题
weight = [2, 2, 4, 6, 3]
n = 5
max_allowed_weight = 9
cur_max_weight = -1
#备忘录, n行max_allowed_weight+1列
flag = [[False]*(max_allowed_weight+1)]*n
p = ZeroOneBag(weight, n, max_allowed_weight, cur_max_weight, flag)
p.backtracking(0, 0, [])
print(p.cur_max_weight,)
使用备忘录，将原本需要计算的45个状态，缩减到23个，效率大幅度提高。
3. 动态规划的思路
使用备忘录的方式，从执行效率上来讲，和动态规划基本没有差异了。但是动态规划是一种新的思考问题的思路。我们一起来看下。
假设物品有n个，我们把问题的求解过程拆分为n个阶段，每个阶段决策一个物品是否放入背包，每次决策(物品放或不放入背包)过后，背包中的物品会出现不同的结果(状态)。每种状态对应递归树中的一个节点，我们去除重复的节点后，每一次决策会得到一个状态结果集合，每次决策就是从一个集合到另外的一个状态集合。
我们用数组[n][max_allowed_weight+1]表示每一次决策后的状态，每一次决策后的状态数不超过max_allowed_weight+1种。
# 0-1背包问题
weight = [2, 2, 4, 6, 3]
n = 5
max_allowed_weight = 9
cur_max_weight = -1
class ZeroOneBag(object):
def __init__(self, weight, n, max_allowed_weight, cur_max_weight, flag):
self.weight = weight
self.n = n
self.max_allowed_weight = max_allowed_weight
self.cur_max_weight = cur_max_weight
self.flag = flag
def dp(self):
"""
动态规划的解法
"""
self.flag[0][0] = True
if self.weight[0] <= self.max_allowed_weight:
self.flag[0][self.weight[0]] = True
for i in range(1, self.n):
for j in range(self.max_allowed_weight+1):
#针对上一次决策的结果进行下一轮的决策：不放物品或者放物品
if self.flag[i-1][j]:
self.flag[i][j] = True
if j+self.weight[i] <= self.max_allowed_weight:
self.flag[i][j+self.weight[i]] = True
for i in range(self.max_allowed_weight, -1, -1):
if self.flag[n-1][i]:
print(i)
return i
if __name__ == '__main__':
# 0-1背包问题
weight = [2, 2, 4, 6, 3]
n = 5
max_allowed_weight = 9
cur_max_weight = -1
flag = [[False]*(max_allowed_weight+1)]*n
p = ZeroOneBag(weight, n, max_allowed_weight, cur_max_weight, flag)
p.dp()
实际上，这里面的二维数组还可以进一步优化，只用一个一维数组即可。
# 0-1背包问题
weight = [2, 2, 4, 6, 3]
n = 5
max_allowed_weight = 9
cur_max_weight = -1
class ZeroOneBag(object):
def __init__(self, weight, n, max_allowed_weight, cur_max_weight, flag):
self.weight = weight
self.n = n
self.max_allowed_weight = max_allowed_weight
self.cur_max_weight = cur_max_weight
self.flag = flag
def dp(self):
"""
动态规划的解法
"""
self.flag[0] = True
if self.weight[0] <= self.max_allowed_weight:
self.flag[self.weight[0]] = True
for i in range(1, self.n):
for j in range(self.max_allowed_weight+1):
if self.flag[j]:
if j+self.weight[i] <= self.max_allowed_weight:
self.flag[j+self.weight[i]] = True
for i in range(self.max_allowed_weight, -1, -1):
if self.flag[i]:
print(i)
return i
if __name__ == '__main__':
# 0-1背包问题
weight = [2, 2, 4, 6, 3]
n = 5
max_allowed_weight = 9
cur_max_weight = -1
flag = [False]*(max_allowed_weight+1)
p = ZeroOneBag(weight, n, max_allowed_weight, cur_max_weight, flag)
p.dp()
当然，这里可以从大到小进行判断，可以节省一些赋值计算。
网友评论