01背包

文章目錄

• 作用
• 前置知識
• 詳解
• • 二維
  • 一維
• 例題

漢語名：01背包

時間複雜度： O ( n m ) O(nm) O(nm)

• 部落格園

作用

給定 n n n個數，求得這些數能否組成 m m m，每個數隻能用一次。

前置知識

• //IT已入門還未入土

詳解

我們定義 v [ i ] v[i] v[i]為第 i i i個數， f f f數組用來存狀态。

算需要多次用 v v v數組更新 f f f數組。

為了友善，用 v v v數組中的一個元素周遊更新整個 f f f數組被筆者稱為一輪。

二維

思路：當我們考慮能否用前 i i i個數組成數 j j j的時候，我們隻需要考慮兩種情況：

• 用前 i − 1 i-1 i−1個數，能組成數 j j j。
• 用前 i − 1 i-1 i−1個數，能組成數 j − v [ i ] j-v[i] j−v[i]。

滿足以上任意一種情況，答案即為肯定。

轉移方程： f [ i ] [ j ] = f [ i − 1 ] [ j ]   o r   f [ i − 1 ] [ j − v [ i ] ] / / 這 裡 f [ i ] [ j ] 表 示 能 否 用 前 i 個 數 組 成 f[i][j]=f[i-1][j]\,or\,f[i-1][j-v[i]]//這裡f[i][j]表示能否用前i個數組成 f[i][j]=f[i−1][j]orf[i−1][j−v[i]]//這裡f[i][j]表示能否用前i個數組成

注意開始時 f [ 0 ] [ 0 ] = t r u e f[0][0]=true f[0][0]=true，其他為 f a l s e false false

一維

剛才的辦法需要我們開一個二維數組，考慮把它優化成一維。

不難發現，由于我們将 i i i按順序枚舉，那麼第一維的 i i i也就失去了意義。

于是我們得到轉移方程： f [ j ] = f [ j ]   o r   f [ j − v [ i ] ] / / 這 裡 f [ j ] 表 示 用 當 前 枚 舉 過 的 數 能 否 組 成 j f[j]=f[j]\,or\,f[j-v[i]]//這裡f[j]表示用目前枚舉過的數能否組成j f[j]=f[j]orf[j−v[i]]//這裡f[j]表示用目前枚舉過的數能否組成j

開始時有且僅有 f [ 0 ] f[0] f[0]的值為 t r u e true true。

但是注意：當我們枚舉 j j j的時候，我們需要倒序枚舉，否則會被目前 i i i作出的決策影響。

舉個例子：開始整個 f f f數組為 f a l s e false false，當我們讀入 1 1 1時，如果按順序枚舉 j j j

j = 1 j=1 j=1， f [ j − 1 ] = t r u e f[j-1]=true f[j−1]=true，是以 f [ j ] f[j] f[j]指派為 t r u e true true

j = 2 j=2 j=2， f [ j − 1 ] = t r u e f[j-1]=true f[j−1]=true（在上一步已經被指派為 t r u e true true了），是以 f [ j ] f[j] f[j]指派為 t r u e true true

j = 3 j=3 j=3， f [ j − 1 ] = t r u e f[j-1]=true f[j−1]=true（在上一步已經被指派為 t r u e true true了），是以 f [ j ] f[j] f[j]指派為 t r u e true true

j = 4 j=4 j=4， f [ j − 1 ] = t r u e f[j-1]=true f[j−1]=true（在上一步已經被指派為 t r u e true true了），是以 f [ j ] f[j] f[j]指派為 t r u e true true

……

顯然，這樣我們就将一個數運用了很多遍，不符合要求。

原因：當我們枚舉到 f [ j ] f[j] f[j]的時候， f [ j − v [ i ] ] f[j-v[i]] f[j−v[i]]已經不是原來的 f [ j − v [ i ] ] f[j-v[i]] f[j−v[i]]而是已經被目前的 v [ i ] v[i] v[i]更新過的。

可以發現：由于 f [ j ] f[j] f[j]僅僅由原來的 f [ j ] f[j] f[j]和 f [ j − v [ i ] ] f[j-v[i]] f[j−v[i]]得到。

是以當有 j < k j<k j<k時， f [ k ] f[k] f[k]的值不會影響到 f [ j ] f[j] f[j]。

是以我們将 j j j倒序枚舉，由于 j j j在不斷變小，本輪已經更新過的都比目前的 j j j大，是以不會被本輪的 v [ i ] v[i] v[i]更新過的值影響到。

關于代碼，筆者會在每道例題裡講。

例題

• [NOIP普及組2011]裝箱問題