动态规划求解0-1背包问题

问题描述

利用动态规划法求0-1背包问题。有n = 20个物品,背包最大可装载M = 878 Kg。物品重量和价值分别如下:
W = {92 ,4 ,43 ,83 ,84 ,68 ,92 ,82 ,6 ,44 ,32 ,18 ,56 ,83 ,25 ,96 ,70 ,48 ,14 ,58},
V = {44 ,46 ,90 ,72 ,91, 40 ,75 ,35 ,8 ,54 ,78 ,40 ,77 ,15 ,61 ,17 ,75 ,29 ,75 ,63},
求最优背包价值。

核心

  1. 初始化状态转移矩阵
  2. 建立状态转移方程
状态转移方程

状态转移方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

'''

'''
def dynamic_programming(bag_weight, goods_weight, goods_value):
# 动态规划状态转移矩阵 20 * 878, 每一行代表一个物品,每一列代表背包重量,每个元素代表背包重量代表的最大价值,并且第二行的值只能选前两个物品
status_matrix = [[0 for i in range(bag_weight + 1)] for j in range(len(goods_value) + 1)]
for row_index in range(1, len(status_matrix)):
for col_index in range(1, len(status_matrix[0])):
# 如果可以放下当前物品
if col_index >= goods_weight[row_index - 1]: # 注意这里有等号
# 取两者的最大值,也就是上一行当前列或上一行减去当前物品重量对于列的值
status_matrix[row_index][col_index] = max(status_matrix[row_index-1][col_index],
status_matrix[row_index-1][col_index-goods_weight[row_index-1]] + goods_value[row_index-1])
else:
# 如果放不下当前物品
status_matrix[row_index][col_index] = status_matrix[row_index-1][col_index]

# 返回最大收益
for i in status_matrix:
print(i)
return status_matrix[-1][-1]


if __name__ == '__main__':
weight = [92, 4, 43, 83, 84, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58]
value = [44, 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63]
max_value = dynamic_programming(878, weight, value)
print(max_value)