動(dòng)態(tài)規(guī)劃專(zhuān)題
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 件了，要么裝、要么不裝就這兩種選擇：裝的話(huà)，新的狀態(tài)要在之前的價(jià)值上添加新物品的價(jià)值；不裝的話(huà)，那么新?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)大牛的整理專(zhuān)題，在他們的引領(lǐng)下熟悉這些題目的套路，先學(xué)習(xí)、掌握要點(diǎn)后再通過(guò)練習(xí)來(lái)提高熟練度。
