python动态规划算法的使用过程
使用过程
1、获取相应信息
(商品数量、背包容积、各商品体积和价值)
2、结构的最佳值矩阵。
3、初始化的最佳值矩阵
(上方和左侧留有空白矩阵作为后续运算,但没有结果)
4、根据商品之间的最佳价值公式计算出相应的结果。
5、逆向推导矩阵得到某个商品,或者没有安装。
输出结果。
实例
print('请输入待装物品数量和背包体积(空格隔开):') n,v=map(int,input().split())#获取物品数量和背包体积 goods=[]#初始化商品列表 foriinrange(n): print(f'请输入第{i+1}个物品的重量和价值(空格隔开):') goods.append(list(map(int,input().split())))#获取商品信息 #计算最优值矩阵 dp=[[0foriinrange(v+1)]forjinrange(n+1)]#初始化最优值矩阵 foriinrange(1,n+1): forjinrange(1,v+1): dp[i][j]=dp[i-1][j]#默认不装,即和上一项最优值相等 ifj>=goods[i-1][0]: #如果背包剩余空间充足 dp[i][j]=max(dp[i][j],dp[i-1][j-goods[i-1][0]]+ goods[i-1][1])#对比装与不装的价值并选择较大值 """ #输出最优值矩阵 foriindp: print(i) """ #计算最优解 x=[0foriinrange(n+1)]#初始化物品状态,0:不装,1:装 foriinrange(n,0,-1): ifdp[i][v]==dp[i-1][v]:#判断最优值是否发生变化,如果没有变化,则说明没有装 x[i]=0#不装 else:#如果有变化,则说明装了,并减去对应重量 x[i]=1#装 v-=goods[i-1][0]#减去对应重量 x[n]=1ifdp[n][v]!=0else0#判断最后一个物品装不装 #输出最优解 print('背包应装物品为:') foriinrange(1,n+1): print(f'编号:{str(i)}\t重量:{goods[i-1][0]}\t价值:{goods[i-1][1]}\n'ifx[i]==1else'',end='') #输出最优值 print('物品价值:',dp[-1][-1])
以上就是python动态规划算法的使用过程,希望对大家有所帮助。更多python学习指路:python基础教程
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。