品易云推流 关闭
文章 > Python基础教程 > python动态规划算法的使用过程

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

头像

小妮浅浅

2021-04-27 17:27:42679浏览 · 0收藏 · 0评论

1、使用过程

获取相应信息(商品数量、背包容积、各商品体积和价值)

结构的最佳值矩阵。

初始化的最佳值矩阵(上方和左侧留有空白矩阵作为后续运算,但没有结果)

根据商品之间的最佳价值公式计算出相应的结果。

逆向推导矩阵得到某个商品,或者没有安装。

输出结果。

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])

以上就是python动态规划算法的使用过程,希望对大家有所帮助。更多Python学习指路:python基础教程

关注公众号

关注公众号,随时随地在线学习

本教程部分素材来源于网络,版权问题联系站长!

底部广告图 底部广告图按钮