python动态规划算法的使用过程

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基础教程

声明:本站所有文章,如无特殊说明或标注,均为爬虫抓取以及网友投稿,版权归原作者所有。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧