背包問題

簡介

背包問題一個很著名的動態規劃問題，也稱為0-1背包問題，很多題都是以此為模板進行魔改的。

問題描述

有N個重量為w1，w2，w3，，，wn且價值為v1，v2，v3，，，vn的物品和一個承重量為W的背包，求讓背包里裝入的物品具有最大的價值總和的物品子集。

題解思路

看到這種最優解求解的題目，很容易想到動態規劃思路。為了設計動態規劃算法，需要推導出一個遞推關系以構造遞推函數，用較小子問題的解的形式來表示背包問題的當前問題的解。

首先考慮一個有前$i$($1\le i\le N$)個物品定義的實例，物品的重量分別為$w_1，w_2，，，w_i$，價值為$v_1，v_2，，，v_i$，背包目前的承重量為$j$($1\le j\le W$)。

設$F(i,j)$為組成該實例最優解的物品的總價值，也就是說能夠放進承重量為$j$的背包中的前$i$個物品中最有價值的子集的總價值。（注意，在這里還沒有出現題目想要的解的形式，）

在這里，可以把前$i$個物品中能夠放進承重量為$j$的背包中的子集分為兩種類別：包括第$i$個物品的子集和不包括第$i$個物品的子集。于是可以得到以下結論：

• 根據定義，在不包括第$i$個物品的子集中，最優子集的價值是$F(i?1,j)$。
• 在包括第i個物品的子集中（$j?w_i\ge 0$)，最優子集為該物品和前$i?1$個物品中能夠放進承重量為$j?w_i$的背包的最優子集組成。這種最優子集的總價值等于$v_i+F(i?1,j?w_i)$。

因此，在前i個物品中，最優解的總價值等于以上兩種情況的最大值，這就是最優子結構了。當然，如果第$i$個物品不能放進背包中，那么從前i個物品中選出的最優子集的總價值即等于從前$i?1$個物品中選出的最優子集的總價值。于是得到下面的遞推式，也是狀態轉移函數。
$$F(i,j)=max\{F(i?1,j),v_i+F(i?1,j?w_i)\},j?w_i>=0$$
$$F(i,j)=F(i?1,j),j?w_i<0$$

同時可以得到邊界。
$$F(0,j)=0,j>=0$$
$$F(i,0)=0,i>=0$$

至此，動態規劃的三要素尋找完成，我們的目標不僅僅是求F的值，還有$F$取值時的物品組合。

實例分析

假設物品數量為5，背包承重量為10，各個物品信息如下表。

物品編號重量w價值v

1	2	6
2	2	3
3	6	5
4	5	4
5	4	6

動態規劃的原理與分治法常常類似，但是分治法將子問題和子子問題反復求解多次，動態規劃擅長的則是記錄之前問題的解，即填表。

承重量

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 6, 6, 6, 6, 6, 0, 6, 0, 6]

[0, 0, 0, 0, 9, 9, 9, 0, 0, 0, 9]

[0, 0, 0, 0, 0, 9, 9, 0, 0, 0, 14]

[0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 14]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15]

可以看到，當輸入為5,10的時候，最優解為15，這是正確的。

回溯求序列

一般，動態規劃用來求最優解，利用遞歸構造可以很方便的找到最后的答案。注意：一旦，動態規劃的題目出現輸入序列，那么就不是找到答案那么簡單，除了正向找到最優解，構造解表，還要反向尋找最優解的構成。 以上面這個例子為例，最后rst[5,10]是15，這是答案，此時定義一個物品長度的序列x并使每個元素為False。

對表格的每一行做遍歷，指定w為最高權重10。逆序遍歷表格每一行，最后一行根據函數判斷rst[m][w]（m為遍歷下標）是否等于rst[m-1][w]若相等，則代表當前行對應的物品沒有選中（原理是依據狀態轉移函數），否則代表選中，w-=當前行對應物品的權重，x[m]置為True，按此順序，遍歷結束。輸出為True的對應下標，即為最優解序列。在這個過程中x的取值要么為True要么為False，這就是為什么叫做0-1背包問題。

def bag(i, j, w, v, out):if i == 0 and j >= 0:out[i][j] = 0return 0if i >= 0 and j == 0:out[i][j] = 0return 0if j - w[i-1] >= 0:out[i][j] = max(bag(i-1, j, w, v, out), v[i-1] + bag(i-1, j-w[i-1], w, v, out))return out[i][j]if j - w[i-1] < 0:out[i][j] = bag(i-1, j, w, v, out)return out[i][j]def search(rst, i, j):x = [False for m in range(i+1)]for m in range(i, -1, -1):if rst[m][j] == rst[m-1][j]:# 此時代表沒有選中當前passelse:x[m] = Truej -= w[m-1]for i in range(len(x)):if x[i]:print("選擇了第{}個物品".format(i))if __name__ == '__main__':# 物品數目i = 5# 背包容量j = 10# 物品信息w = [2, 2, 6, 5, 4]v = [6, 3, 5, 4, 6]# 結果存放表rst = [[0 for m in range(j+1)] for n in range(i+1)]# 計算結果，構造解集合bag(5, 10, w, v, out=rst)# 輸出解集合表格for item in rst:print(item)# 回溯查找輸入序列search(rst, i, j)

當然本題也可以使用非遞歸的方式實現，也就是我們更常用的DP Table的形式，代碼如下。

def bag(N, W, w, v, dp):for i in range(1, N+1):for j in range(1, W+1):if w[i-1] <= j:dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])else:# 第i個物品放不下dp[i][j] = dp[i-1][j]return dpdef search(rst, i, j):x = [False for m in range(i+1)]for m in range(i, 0, -1):if rst[m][j] == rst[m-1][j]:# 此時代表沒有選中當前passelse:x[m] = Truej -= w[m-1]for i in range(len(x)):if x[i]:print("選擇了第{}個物品".format(i))if __name__ == '__main__':# 物品數目i = 5# 背包容量j = 10# 物品信息w = [2, 2, 6, 5, 4]v = [6, 3, 5, 4, 6]# 結果存放表dp = [[0 for m in range(j+1)] for n in range(i+1)]# 計算結果，構造解集合bag(5, 10, w, v, dp)# 輸出解集合表格for item in dp:print(item)# 回溯查找輸入序列search(dp, i, j)

優化思路

其實可以從代碼和狀態轉移公式都能看出來當前層的狀態只與上一層狀態有關（可以參考上一節的DP Table可視化），也就是說，我們其實只需要知道最后一層的情況而不需要存儲之前的結果，在dp table中我們最后輸出的其實是最右下角的值。這就是01背包的狀態壓縮。

這個時候，我們可以得到一個新的遞推式，這里的$f[j?w[i]]+v[i]$代替了原來遞推式中的$dp[i?1][j?w[i]]+v[i]$這部分。

$$f[j]=max\{f[j],f[j?w[i]]+v[i]\}$$

但是注意，我們這里只有一維數組，這就要保證當我想要取得$f[j?w[i]]$的時候，他沒有被更新過，換言之，它必須是上一層的數據，這就要求我們內部的那個循環必須逆序進行。 這就是空間優化版本最難以理解的地方。

具體代碼如下，此時就不能采用上面的思路輸出選擇的物品了。此時空間復雜度由$O(NW)$優化為$O(W)$。

def bag(N, W, w, v, dp):for i in range(N):for j in range(W, w[i]-1, -1):dp[j] = max(dp[j], dp[j-w[i]] + v[i])return dpif __name__ == '__main__':# 物品數目i = 5# 背包容量j = 10# 物品信息w = [2, 2, 6, 5, 4]v = [6, 3, 5, 4, 6]# 結果存放表dp = [0 for m in range(j+1)]# 計算結果，構造解集合dp = bag(i, j, w, v, dp)print(dp[-1])

補充說明

具體代碼可以查看我的Github，歡迎Star或者Fork。參考書《你也能看得懂的Python算法書》，書中略微有一點不合理之處，做了修改。到這里，其實你已經體會到了動態規劃的簡約之美。

總結

以上是生活随笔為你收集整理的动态规划算法-03背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。