python動態(tài)規(guī)劃算法怎么用

小編給大家分享一下python動態(tài)規(guī)劃算法怎么用，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

python有哪些常用庫

python常用的庫：1.requesuts；2.scrapy；3.pillow；4.twisted；5.numpy；6.matplotlib；7.pygama；8.ipyhton等。

1、使用過程

獲取相應(yīng)信息(商品數(shù)量、背包容積、各商品體積和價值)

結(jié)構(gòu)的最佳值矩陣。

初始化的最佳值矩陣(上方和左側(cè)留有空白矩陣作為后續(xù)運算，但沒有結(jié)果)

根據(jù)商品之間的最佳價值公式計算出相應(yīng)的結(jié)果。

逆向推導矩陣得到某個商品，或者沒有安裝。

輸出結(jié)果。

2、實例

print('請輸入待裝物品數(shù)量和背包體積(空格隔開):')
n, v = map(int, input().split())  # 獲取物品數(shù)量和背包體積
goods = []  # 初始化商品列表
for i in range(n):
    print(f'請輸入第{i + 1}個物品的重量和價值(空格隔開):')
    goods.append(list(map(int, input().split())))  # 獲取商品信息
 
# 計算最優(yōu)值矩陣
dp = [[0 for i in range(v + 1)] for j in range(n + 1)]  # 初始化最優(yōu)值矩陣
for i in range(1, n + 1):
    for j in range(1, v + 1):
        dp[i][j] = dp[i - 1][j]  # 默認不裝，即和上一項最優(yōu)值相等
        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])  # 對比裝與不裝的價值并選擇較大值
 
"""
# 輸出最優(yōu)值矩陣
for i in dp:
    print(i)
"""
 
# 計算最優(yōu)解
x = [0 for i in range(n + 1)]  # 初始化物品狀態(tài)，0：不裝，1：裝
for i in range(n, 0, -1):
    if dp[i][v] == dp[i - 1][v]:  # 判斷最優(yōu)值是否發(fā)生變化，如果沒有變化，則說明沒有裝
        x[i] = 0  # 不裝
    else:  # 如果有變化，則說明裝了，并減去對應(yīng)重量
        x[i] = 1  # 裝
        v -= goods[i - 1][0]  # 減去對應(yīng)重量
    x[n] = 1 if dp[n][v] != 0 else 0  # 判斷最后一個物品裝不裝
 
# 輸出最優(yōu)解
print('背包應(yīng)裝物品為：')
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='')
# 輸出最優(yōu)值
print('最大物品價值:', dp[-1][-1])

看完了這篇文章，相信你對“python動態(tài)規(guī)劃算法怎么用”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！