動(dòng)態(tài)規(guī)劃專題

https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-xiang-jie-jin-

「0-1背包問(wèn)題描述」

現(xiàn)在有一個(gè)可裝載重量為 W 的背包和 N 個(gè)物品滑凉，每個(gè)物品有重量和價(jià)值兩個(gè)屬性。其中第 i 個(gè)物品的重量為 wt[i-1]喘帚，價(jià)值為 val[i-1]畅姊，現(xiàn)在讓你用這個(gè)背包裝物品，最多能裝的價(jià)值是多少吹由？

例如：

W = 10, N = 5

wt = [2, 2, 6, 5, 4]

val = [6, 3, 5, 4, 6]

返回 15若未，因?yàn)榭梢匝b [2,2,4] 重量的物品，價(jià)值分別 [6,3,6]

題目中 0-1 指的是背包裝物品時(shí)倾鲫，要么裝整個(gè)物品粗合、要么不裝，不能只裝取部分乌昔。

題目分析

因?yàn)楸嘲兄亓肯拗葡毒危援?dāng)我們遍歷物品時(shí)，無(wú)法確定物品是否被裝入背包磕道，就更難以找到裝某一物品時(shí)與之前狀態(tài)的關(guān)聯(lián)供屉。動(dòng)態(tài)規(guī)劃會(huì)強(qiáng)調(diào)“狀態(tài)”，通過(guò)自定義的一維或二維數(shù)組為我們將物品裝入背包這個(gè)行為定義成狀態(tài)的變化，從而找到與上一次裝物品之間的關(guān)聯(lián)伶丐。

動(dòng)態(tài)規(guī)劃英文 dynamic programming悼做，所以定義相關(guān)的狀態(tài)數(shù)組多用 dp, 本題目中就是通過(guò)定義二維數(shù)組、在 Python 中即嵌套列表來(lái)實(shí)現(xiàn)撵割。

背包問(wèn)題中贿堰，用 dp [ i ] [ j ] 表示在物品列表中的前 i 件物品操作完、此時(shí)背包容量為 j 的狀態(tài)下啡彬，背包所能裝的最大價(jià)值羹与，恰好對(duì)應(yīng)了題目所求，求容量為 W 的背包庶灿、 N 個(gè)物品所實(shí)現(xiàn)最大價(jià)值即 dp [ N ] [ W ]? 對(duì)應(yīng)的值纵搁。

為何要定義這么一個(gè)奇怪的狀態(tài)呢？就是為了找尋裝物品時(shí)不同狀態(tài)間的關(guān)系往踢，從而建立狀態(tài)轉(zhuǎn)移方程腾誉。在裝第 i 件物品時(shí)，對(duì)應(yīng)題目中的重量和價(jià)值列表峻呕，該物品重量為 wt[i-1]利职、價(jià)值為 val[i-1]。

在操作這第 i 件物品之前瘦癌，背包狀態(tài)處于 dp [ i-1 ] [ j ] 猪贪，物品 -1、容量不變讯私。進(jìn)行到第 i 件了热押，要么裝、要么不裝就這兩種選擇：裝的話斤寇，新的狀態(tài)要在之前的價(jià)值上添加新物品的價(jià)值桶癣；不裝的話，那么新?tīng)顟B(tài)與之前狀態(tài)的價(jià)值是相等的娘锁。這便是背包問(wèn)題狀態(tài)轉(zhuǎn)移關(guān)鍵所在牙寞。有種建立遞歸關(guān)系的意思，所以要找到初始狀態(tài)值莫秆，在 i = 0 或 j = 0 時(shí)碎税，一個(gè)是 0 件物品、一個(gè)是背包容量為 0馏锡，其價(jià)值對(duì)應(yīng)為 0雷蹂。之后的狀態(tài)值在此基礎(chǔ)上可以不斷找到得出。

代碼實(shí)現(xiàn)

因?yàn)楸绢}不是 LeetCode 原題杯道，所以解法代碼沒(méi)有沿用 Class 那種格式匪煌，只是定義了函數(shù)：

# n 對(duì)應(yīng)個(gè)數(shù)责蝠，c 對(duì)應(yīng)背包容量，w 為物品重量列表萎庭，v 物品價(jià)值列表

def bag_value(n,c,w,v):

? # 嵌套的列表解析式生成 c x n 的二維數(shù)組霜医、列表

? ? dp = [[None for j in range(c+1)] for i in range(n+1)]

? ? # 為初始狀態(tài) i=0 或 j=0 時(shí)賦值 0

? ? for i in range(n+1):

? ? ? ? for j in range(c+1):

? ? ? ? ? ? if i == 0:

? ? ? ? ? ? ? ? dp[i][j]=0

? ? ? ? ? ? if j == 0:

? ? ? ? ? ? ? ? dp[i][j]=0

? ? # 仍然遍歷二維數(shù)組? ? ? ? ? ?

? ? for i in range(1,n+1):

? ? ? ? for j in range(1,c+1):

? ? ? ? ? # 若背包容量小于要裝的物品重量，那么該物品不會(huì)被裝入驳规、狀態(tài)不變

? ? ? ? ? ? if j<w[i-1]:

? ? ? ? ? ? ? ? dp[i][j] = dp[i-1][j]

? ? ? ? ? ? # 若有可能裝該物品肴敛，取裝或不裝該物品狀態(tài)下最大價(jià)值

? ? ? ? ? ? else:

? ? ? ? ? ? ? ? dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1],dp[i-1][j])

? ? # 最終返回 n、c 值下的 dp 價(jià)值

? ? return dp[n][c]

n = 5

c = 10

w = [2, 2, 6, 5, 4]

v = [6, 3, 5, 4, 6]

result = bag_value(n,c,w,v)

# 可以得到 result 值為 15

這里值得注意的是吗购，在不確定是否裝該物品時(shí)医男，對(duì)上一個(gè)狀態(tài)的取值并沒(méi)有取我們之前提到的 dp [ i-1 ] [ j ] 而是對(duì)這里的背包容量處理、調(diào)整至最大容量減去第 i 件物品的重量捻勉，這是為了保證裝完該物品后不超出背包容量限制镀梭，而 dp 本身對(duì)背包容量是有遍歷的，所以選取的是最精準(zhǔn)的上一狀態(tài)踱启。

感想

刷題刷到動(dòng)態(tài)規(guī)劃报账，很大的感受是我這刷題實(shí)施得太晚了，早幾年就好了埠偿，之前對(duì)這些概念透罢、算法完全沒(méi)有意識(shí)。現(xiàn)在補(bǔ)過(guò)冠蒋，只能說(shuō)好過(guò)之后來(lái)補(bǔ)羽圃。

同時(shí)，潛意識(shí)里就覺(jué)著動(dòng)態(tài)規(guī)劃很難浊服，所以選的策略是跳出題目统屈，看有經(jīng)驗(yàn)大牛的整理專題胚吁，在他們的引領(lǐng)下熟悉這些題目的套路牙躺，先學(xué)習(xí)、掌握要點(diǎn)后再通過(guò)練習(xí)來(lái)提高熟練度腕扶。