動(dòng)態(tài)規(guī)劃就是，將任務(wù)每一步均記錄下來，以便將來重復(fù)使用時(shí)能夠直接調(diào)用

問題描述：給定n個(gè)物品，每個(gè)物品的重量是Wi,價(jià)值是Vi，但是背包最多能裝下capacity重量的物品，問我們?nèi)绾芜x擇才能利益最大化。

這里涉及到建模過程，本文章主要講解代碼實(shí)現(xiàn)，建模過程較為簡(jiǎn)略。

使用dp[i][j]來表示在容量為j的情況下，前i件物品的最大化利益。

情況一：放入第i件物品前，發(fā)現(xiàn)j<weight[i]，因此dp[i][j]此時(shí)仍然是dp[i-1][j]（也就是dp[i][j]沒有發(fā)生變化）。
情況二：放入第i件物品時(shí)，發(fā)現(xiàn)j >= weight[i]，此時(shí)你放入這件物品與否要看放進(jìn)去以后利益是如何變化的。
①不放入，那么dp[i][j]的值還是dp[i-1][j]。
②放入，那么dp[i][j]的值是dp[i-1][j-weight[i]]+value[i]。（想一想對(duì)不對(duì)）

那么具體實(shí)現(xiàn)代碼如下

import numpy as np


weight = [1,2,5,6,7,9]
value = [1,6,18,22,28,36]

num = 6
capicity = 13


def fun(num, capicity, weight, value):
    #構(gòu)造一個(gè)num+1行，capicity+1列的二維數(shù)組
    #便于下標(biāo)從1開始使用
    dp = np.array([[0]*(capicity+1)]*(num+1))
 

    #dp[i][j]表示第前i件物品在容量為j下的最大價(jià)值
    #最終需要知道dp[num][capicity]也就是dp[6][13]，在容量為13情況下前6件物品的最大價(jià)值是多少。
    #進(jìn)一步的需要知道dp[][]
    for j in range(1, capicity+1):
        for i in range(1,num+1):
            if j >= weight[i-1]:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1])
            else:
                dp[i][j] = dp[i-1][j]

    print(dp)

fun(num, capicity, weight, value)

核心就在于這個(gè)動(dòng)態(tài)轉(zhuǎn)移方程。

d p [ i ] [ j ] = m a x { d p [ i ? 1 ] [ j ] , d p [ i ? 1 ] [ j ? w e i g h t [ i ] ] + v a l u e [ i ] } dp[i][j] = max\{dp[i-1][j],dp[i-1][j-weight[i]]+value[i]\} dp[i][j]=max{dp[i?1][j],dp[i?1][j?weight[i]]+value[i]}

雖寫下這篇筆記，但有關(guān)動(dòng)態(tài)規(guī)劃的問題還需多多研究，加深理解。文章來源地址http://www.zghlxwxcb.cn/news/detail-733502.html

到了這里，關(guān)于數(shù)學(xué)建模__動(dòng)態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！