0-1背包问题 Python 动态规划

文章目录
基于动态规划算法的 0 − 1 0-1 0−1 背包问题设计过程与实现
1. 算法设计
1.1 构造*优值矩阵
1.2 计算*优解
2. 算法实现-完整代码
3. 程序测试
输入值
输出值
测试结果
基于动态规划算法的 0 − 1 0-1 0−1 背包问题设计过程与实现
1. 算法设计
获取对应信息（商品数量，背包容积，各商品的体积和价值）
构造*优值矩阵
初始化*优值矩阵（上方和左侧留有一列空白矩阵用作后续运算，但不做结果使用）
根据商品之间的*优值公式计算得出相应的结果
通过逆向推导矩阵得到某件商品装了或是没有装
输出结果
1.1 构造*优值矩阵
# 计算*优值矩阵
dp = [[0 for i in range(v+1)] for j in range(n+1)] # 初始化*优值矩阵
for i in range(1, n+1):
for j in range(1, v+1):
dp[i][j] = dp[i-1][j] # 默认不装，即和上一项*优值相等
if j >= goods[i-1][0]:
# 如果背包剩余空间充足
dp[i][j] = max(dp[i][j], dp[i – 1][j-goods[i-1][0]] +
goods[i-1][1]) # 对比装与不装的价值并选择较大值

1.2 计算*优解
# 计算*优解
x = [0 for i in range(n+1)] # 初始化物品状态，0：不装，1：装
for i in range(n, 0, -1):
if dp[i][v] == dp[i-1][v]: # 判断*优值是否发生变化，如果没有变化，则说明没有装
x[i] = 0 # 不装
else: # 如果有变化，则说明装了，并减去对应重量
x[i] = 1 # 装
v -= goods[i-1][0] # 减去对应重量
x[n] = 1 if dp[n][v] != 0 else 0 # 判断*后一个物品装不装

2. 算法实现-完整代码
print(‘请输入待装物品数量和背包体积(空格隔开):’)
n, v = map(int, input().split()) # 获取物品数量和背包体积
goods = [] # 初始化商品列表
for i in range(n):
print(f’请输入第{i + 1}个物品的重量和价值(空格隔开):’)
goods.append(list(map(int, input().split()))) # 获取商品信息

# 计算*优值矩阵
dp = [[0 for i in range(v + 1)] for j in range(n + 1)] # 初始化*优值矩阵
for i in range(1, n + 1):
for j in range(1, v + 1):
dp[i][j] = dp[i – 1][j] # 默认不装，即和上一项*优值相等
if j >= goods[i – 1][0]:
# 如果背包剩余空间充足
dp[i][j] = max(dp[i][j], dp[i – 1][j – goods[i – 1][0]] +
goods[i – 1][1]) # 对比装与不装的价值并选择较大值

“””
# 输出*优值矩阵
for i in dp:
print(i)
“””

# 计算*优解
x = [0 for i in range(n + 1)] # 初始化物品状态，0：不装，1：装
for i in range(n, 0, -1):
if dp[i][v] == dp[i – 1][v]: # 判断*优值是否发生变化，如果没有变化，则说明没有装
x[i] = 0 # 不装
else: # 如果有变化，则说明装了，并减去对应重量
x[i] = 1 # 装
v -= goods[i – 1][0] # 减去对应重量
x[n] = 1 if dp[n][v] != 0 else 0 # 判断*后一个物品装不装

# 输出*优解
print(‘背包应装物品为：’)
for i in range(1, n + 1):
print(f’编号：{str(i)}\t重量：{goods[i – 1][0]}\t价值：{goods[i – 1][1]}\n’ if x[i] == 1 else ”, end=”)
# 输出*优值
print(‘*大物品价值:’, dp[-1][-1])

3. 程序测试
输入值
请输入待装物品数量和背包体积(空格隔开):
5 10
请输入第1个物品的重量和价值(空格隔开):
2 6
请输入第2个物品的重量和价值(空格隔开):
2 3
请输入第3个物品的重量和价值(空格隔开):
6 5
请输入第4个物品的重量和价值(空格隔开):
5 4
请输入第5个物品的重量和价值(空格隔开):
4 6

输出值
背包应装物品为：
编号：1 重量：2 价值：6
编号：2 重量：2 价值：3
编号：5 重量：4 价值：6
*大物品价值: 15

测试结果
程序运行正确且运行结果符合预期。