使用过程
1、获取相应信息
(商品数量、背包容积、各商品体积和价值)
2、结构的最佳值矩阵。
3、初始化的最佳值矩阵
(上方和左侧留有空白矩阵作为后续运算,但没有结果)
4、根据商品之间的最佳价值公式计算出相应的结果。
5、逆向推导矩阵得到某个商品,或者没有安装。
输出结果。
实例
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])
以上就是python动态规划算法的使用过程,希望对大家有所帮助。更多Python学习指路:python基础教程
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
神龙|纯净稳定代理IP免费测试>>>>>>>>天启|企业级代理IP免费测试>>>>>>>>IPIPGO|全球住宅代理IP免费测试